System and method for a data processing pipeline (USPatent4646075)

United States Patent 11 [1 Patent Number: 4,646,075 Andrews etal. [4s] Date ofPatent: Feb. 24,1987 [54] SYSTEM AND METHOD FOR ADATA (sn ABSTRACT PROCESSING PIPELINE ‘Anelectronic dataprocessing pipeline system and [75] Inventors: David H.Andrews, West Jordan; method forprocessing encoded control points repre- Phillip i.Lack SaltLake City, senting graphical illustrations. Thepipeline comprises a Leland K,Putnam, Taylorsville all number ofseparate micro-programmed circuit cards, ofUah tach ofwhich areprogrammed toperform aspecific processing operation 15AsieRteBahCratonSate earnaatimaecaddefn , {geometrical transformation tobeperformed onthe [21] Appl. No: $48,312 ‘graphical illustration. Thematrixmakercard,together ‘withamatrixmultipliercard,thencalculatestransfor- (22) Filed: Nov. 3,1988 Imation matrix representing thedesired transformation : -GO9G 1/16 Electronic representations ofcontrol datapoints are [82] USC Sao 340/728, thentransmitted tothepipeline forprocessing. These“40/731,440/705;340/724controlpointsate3Dpointscomprisingboththevert- [58]FieldofSearch ............ 340/729, 728,747,731, ceswhichterminate linearedgesoftheillustration and "40/117, 103, 724, 739 thecontrol points corresponding tocurved edges ofthe istration. Each ofthepoints isencoded toindicate whether itrepresentsavertexofacontrolpointfora (6) References Cited ‘curved edge. Inaddition, thevarious points areen- US. PATENT DOCUMENTS Coded toindicate whether thecorresponding portion of Re30785 10/1981 Lovercheck et... 364/200 Whellustration istoberenderedasasolidfigureoine 3,399,401 8/1968 Ellisetal. 340/709 drawing. 3,544,33810/1970 Christensen etal ‘Thecontrol pointsarethenmultiplied bythetransfor- 353439610/1970Haneal ns/e.6 SuesIYIOHanat ZAImatonmarcomputedpreviouslynavectormul Sogn w/97t Wamaek ponvnmnnns BSS ieeieuitcad.Nextthecontrolpointsaeclippedto 31686.876 8/1992 Sutherland ©.” 335/152 theplanesoftheviewingfrustumbyanumberofclip- Soot: 10/t9 Hanson Tieral 178/68 percards (onecardforeach clipping plane). The3D Soave) "7973 Marrson Iet 30/728 Control points arethen mapped onto the2Dviewing376836510/1973.Sete 28/186 SfindowbyaviewportcaraListContinued onnextpage. ‘Oncethecontrolpointshavebeenprocessedassetforth, above,theclippedcontrolpointsarethenexplodedto ornesgenerateapluralityofsmalllinesegmentsrepresenting RPUBLICATIONS eachofthecurvededgesoftheillustration. Asufficient (OnCoons andOther Methods forthe Representation of Sumber oflinesegments aregenerated foreach edge Curved Surfaces: Forrest, 1972; Reprinted inInteractive such thattheedgesoftheillustrationspearsmooth{0 Computer Graphies H.Freeman, Ed.IEEE Cat. No. theviewer, Finally, theappropriate portions ofthe EHO 186-0, 2/80, istration are rendered asaline drawing, inaccor- ListContinued onnext page dance with thecode attached tothevarious control points; andtheprocessed data isthen converted intoa Form which isappropriate forscan conversion. Primary Examiner—Marshall M.Curtis “Attorney, Agent. orFirm--Workman, Nydegger &Sensen 26Claims,47DrawingFigures fl: ipl ee afTEPASEPeat ii+ HERErite iinin intheHa Sono HuialilPraiga ihereilly) |Pa Pu q¢Pei j 4,646,075 Page2 Doct 430398612/98)Las... 364/900 US.PATENT MENTS 4,314,3512/1982Postel€tAl.ocrsenennnnen 340/739 54816726,6/1974Sutherlandeta passe $338192Ponteal some SEB.Lo76/1978.Sutherland Boise $43RNO 71944mand al Or 383.005 1/198 Orbaneta sone 8, vn 3061979/1978. Grover Beast So08.6 12/1978. Swallow wn Mo 3,944,997 3/1976 Swallow sevesensensee MOLTOS- OTHER PUBLICATIONS 3,978,280 8/1976 Kavanaghetal. 178/68 J,D.Foleyetal,Fundamentals ofInteractive Com- Ao1e3624/1999Brstoweta SHA DalerGomghicany.sleaae(OSA.198d) {enaSam Caen a TT.Paviidis, Algorithms forGraphics andImagePro- op9A80.$7978.Grimmea. ne364/200 oodooo 6/1978 Bradevel nn 364900 cessing,pp.215-316(US.A.,1982). 4,107,665 8/1978 Mayeretal. Sproul,RobertF.,Principles ofInteractive Computer Autasaa9/1978Mayeret Graphicsatpp.309-331(24e2.1979). ANAMS/IBTE Mayeretal 273/101.2 NewYorkInstituteofTechnology andComputer S17473.9/1976Habege,I. GraphicsLab,Inc,ComputerGraphicsLab,Inc IDWS WASTE Oboe ~Moms NewYorkInstitute ofTechnology. and.ComputerQUSSSI9SrtoreGupia TTMaa00 GraphicsLab,Inc.,BusinessSeren,“TheElementsof Alenase 9/1999. vane Siaiees StyleinComputerPictures,”(U.S.A,1982). £189832/1900.Shueta 586/93GroveVideoCorporation, TheNewDigitalGraphics Lissa2/1980 Stem= 383 SeemUSAC IID. 41975904/1980 Sukonick ta 364/900 Eacational andIndustrial Television, “Directory of 4208389 5/1980 Heart wor {Zino omepena tai Syna7 Special fects Generators andComputer Graphics4.222048 9/1980Johnson uc 340/747 Systems,” atpp.43-52(U.S.A.,Mar.,2). {225520 9/1080 Stokes won 364/200 Cinetzon Computer Systems, Inc 4225929 9/1980 Ikeda»... 364/521 Microconsultants, Inc., MCI/Quantel News (U.S.A.. {228467 1071980 Gupta etal 364200 Mar 1983){2ie99010/1980Gilllmndetal ewan Mae18arora val . ‘32s‘othSader SamsAtaSystemeduro/100DialVidas Sy iamtere/iselLacy BonnfemProdu 1S.AwABE 4283,7658/1981Riegerooronnnm 364/521_‘Interrand Corporation (U.S.A.,». 4,296,476 10/1981 Mayer €€besnrsnnsn 364/900 ViaVodeo, Inc., System One.SGones1/1981Stembergetal387iea3MAMPBTechnologies, Inc.(Canada,1979) 4,301,472 11/1981 Dans ..noncnncmennennmnen 358/163 Dubner Computer Systems, Inc. (U.S.A., 1981). U.S. Patent Feb.24,1987 Sheet1of334,646,075 ge.|238 «|8we|8 Ble #18 33 58 g 2 5 a & - xe a = . oa 5 fo} iag::°dD<>cy § pled2) 8 y3 333 ge 8 {oe|i U.S. Patent Feb. 24,1987 Sheet2of334,646,075 woe es esi FIG. 1A FIG. 1B U.S.Patent Feb.24,1987 Sheet30f334,646,075 200.\ 201‘CPU 300 ‘806 | za19 ~_a] =e] - FIG. 2 U.S.Patent Feb.24,1987 Sheet40f334,646,075 | 1 I ¥]/ls q Z | coelaa co |! (atestcuePeale ee |:Se fe Aiotic. \3 IR BLfo-nnnnnnnnn nt L Aai ae'| er U.S.Patent Feb.24,1987 Sheet80f334,646,075 Loh een? |(eage=E A | a2Se j tba il 1| oie) E | t!=|| Wyle eth |E} o|E= a Lo 1=nea) LgEl a| aEll Biat a5 =| | Ay |g( |———an|on: ! nee |S| teateaoa eV3 U.S.Patent Feb.24,1987 Sheet90f33 4,646,075 ai"iaooaa Haiera3 |Nir what|éEe S:|— | U.S.Patent Feb.24,1987 Sheet10of334,646,075 in 7J) eu ; BU speli Feil CLTT|ij SEE ||LE eani = eelaes) 2a |f2| U.S.Patent Feb.24,1987 Sheet11of334,646,075 & |A|-i. i | io LyTera |* U.S.Patent Feb.24,1987 Sheet12of334,646,075 EE &a3_988_§821)_— g 3 Cds nana be ot | 1z!| tot ;4|x| a f=|3Sa,|FarSit)s L a atal||& | a c-T_ 3eri|Ha ole al |5 | | are It_—__Jf =2aa8}Aa8a8 U.S. Patent Feb. 24,1987 Sheet13of33.4,646,075 ae 8 8a & i Uy] TRAztSe | [ate Wn Sa mmBaneToa \ U.S. Patent Feb. 24,1987 Sheet 14of33-4,646,075 | 3_ ct |ras ct ak i}|eie ctzo82383az| ff | 3 a | | Arh eyr |ee Ole U.S. Patent Feb.24,1987 Sheet 15of334,646,075 en 4 men] |8 | (|TB ofits|fete ‘Hi: aE |aeee ellMie| [FT p4 U.S.Patent Feb.24,1987 Sheet16of334,646,075 ra | | | ! Pa ! ieee na ||a=| |38|a:HE 2SE}| |n=p 7 U.S.Patent Feb.24,1987 Sheet17of334,646,075 ne mats | | | | ~lefsue|shefeloledstolesey[| | | | i! ||tat '|58 | L le | | || oo. ie)“4oO 424— US. Patent Feb.24,1987 Sheet18of334,646,075 |88.8 a gel a— | iaa |ali, Ig ||a || | i | |{| || U.S.Patent Feb.24,1987 Sheet19of334,646,075 razr] |as. |oe ||eee Ctmete |taa5Tek |ir LI ge ee | US.Patent Feb.24,1987 Sheet20of334,646,075 hea S, FIG. 6 U Dey" U * [eeeef se = ge Ls] [ee@ser [e=y-"° (rs.] bas [e020 move CASE OWA.CODE [Froeessrest] [rrocesecove] 90 [rxceess wet] [rreeess cenenJ] FIG. 7 U.S.Patent Feb.24,1987 Sheet21of334,646,075 [recesserJoes © [ae se FIG.7A © [receen“ © eae [irxenom sete saeeeonanp00 © oo ©)©) FIG. 78 [recesses J~=#* ‘27>a 528 © S) FIG. 7C U.S. Patent Feb.24,1987 Sheet22of334,646,075 Ee=}™ sue [=n] [rsvoor] [eon pO [Ersomen}-ee =333=e [eerrowrina) 2708 ©) FIG. 7D [esrows 0 ae = ©) FIG. 7E U.S.Patent Feb.24,1987 Sheet23of334,646,075 [Exc a= d ©fem eam @) ©) FIG. 7F [v0 ™ ©) © FIG. 7G FIG. 7H U.S.Patent Feb.24,1987 Sheet24of334,646,075 -=r “ see sea 3900 784 nay 6 Sete SS eno henaany E=] [Eat Eee FIG. 71 U.S.Patent Feb.24,1987 Sheet25of334,646,075 [exo J sa 592 és) FIG. 7K ©) FIG. 7J Jsrutit(So.b.52 by Is= . ) FIG. 7L U.S. Patent Feb.24,1987 Sheet26of334,646,075 (rl ae (EEN ea Jrcooe—rast a jocoe~rn tanencr |580 706 ©) S) FIG. 7M [een loonstant ostra(ng8) &) FIG. 7N U.S.Patent Feb.24,1987 Sheet27of33.4,646,075 ¢3$8 og 7oFFf o Lig ° : ° =JiE)[bs ira = re Sg Fy ~3 3. o D1:> H ¢ U.S. Patent Feb. 24,1987 Sheet 28of334,646,075 [iss® -% 23 &- & (ourrur 632[FETmae]=eF- [=e=} R-%pe? in ([errriccom] 631SSwo Less] ves 645b [Smee | FIG. 8C U.S.Patent Feb.24,1987 Sheet29of334,646,075 aRea Re| ae Bgi= Bpescate 5,=5,escate = = =tec Coe5*[85-24 8,82)/4|-637SamBaescave Gyn506-208, -B5)2 B=Boca Eat [Eo+S] /2 Bus (85+53] /2-Sy Cut Sy Gaues Push(Bx.Cn,5.5) eas EZ| [errcrear] Su=[S585cn [[ourer(ay.e) |[fowrrena| Ge)[eere.e | YES 648¢ [Seren saan] FIG.8E oa eas GED FIG. 8D U.S. Patent Feb. 24,1987 Sheet30of334,646,075 U [rec J" encone} [xx] be [aura] [ror |vese Lerma |LemJ e- Ee) Eee) Eee FIG. 9 U.S.Patent Feb.24,1987 Sheet31of334,646,075 [sea] a arseGED. TIT rootn-terwxeyn,.0) 3) . FaePES” |<> 722 fourrureorac]esePS Ga) Gs) “2S [rind axis .dams,cnt=aeav‘781Z [toot(as.x:+aX,C¥1, Oxm3,003)) 776 Se cca) = FIG. 9A U.S.Patent Feb.24,1987 Sheet32of334,646,075 . eooe(vi-aw,x2.200uae]oe wes “<< “ FIG. 9B . U.S. Patent Feb.24,1987 Sheet33of334,646,075 [esse [=e 752(een [een FIG. 9D 743 . “ [eaten] [omerwe)|[ovrcarsa)| [enntens.o|[ener(onso7| Cre) FIG. 9C 4,646,075 1 2 numerous colored figures arethen displayed onavideo SYSTEM AND METHOD FOR ADATA monitor ofother output device $0ast0produce the PROCESSING PIPELINE desired graphical illustration, ‘Although theprior artsystems have greatly facili- ‘Appendices A-S, referred toherein, have been at-$tated thepreparation ofgraphic designsandanimation, tached totheoriginal specification. such systems alsohave anumber ofdrawbacks and disadvantages, especially intermsoftheabilityofsuch BACKGROUNDsystems (0efficiently animate illustrations which have 1.The Field oftheInvention curved lines andsurfaces. Most prior artsystems will This invention relates tocomputerized graphic sys- 10define each curved lineinanillustration interms ofa temsand,moreparticularly, toanovelsystemandrelativelylargenumberofdatapointswhicharethenmethod ofcomputerized graphics inwhich arelatively connected bylinesegments 50thatthelinesegmentsSmallnamberofcontroldatapointsgeneratedbyacollectively approximate thecurvedline.Ifitisdesired parametric function arerapidly processed usinganoveltomodifytheillustrationinordertocreateanimation, Gataprocessing pipeline$0astogeneraterealtime15eachofthedatapointsforeachlinesegmentmustbeanimation ofgraphical illustrations, even though such _re-processed. Forexample, ifthe letter "S”were tobeilustrations maybecomposedofcurvedlinesorcurved enlargedorrotatedaboutanaxis,thenumerousdatasurfaces. pointsusedtoapproximate thecurvesofthe"S”would2.ThePriorArt teachbeprocessed#numberofsuccessivetimes.TheDuringrecentyears,therehasbeenanincreased20largenumberofdatapointswhichmustbeprocessedinterest inthetechnology ofcomputer graphics and greatly increases thestorage capacity required forthe Computer-aided animation. Ithasbeenfound thatsuch system, aswellastheprocessing timewhich isrequired. technology cansignificantly reduce costs andincrease Further, asmentioned above, thedatapoints which productivity inanumber ofdifferent fields areusedtodefinethecurvedlinesusedinanillustration Televisionbroadcasters, forexample,areoftenin25areconnectedbyaseriesofshortlinesegmentswhich needofgraphic designs foruseintheirbroadcasts. This approximates thecurved linesoftheillustration. Itwillisparticularly trueinthecaseofnewsbroadcasts, beappreciated, therefore,thatwhentheillustration is‘where maps andgraphs arefrequently desired inorder enlarged ontheviewing screen, theindividual lineseg-tohelpexplainnewsworthy events.Moreover, inmany__mentsbecomemorevisible,thusrenderingtheillustra-insianees, itisalsodesirable toanimate such graphic 30tionlesssmooth. Ananalogous problem exists when Gesigns andillustrations during thebroadcast. Using attempting toapproximateacurvedsurface.Theprior traditional illustration andanimation methods,how-artsystemshavenotyetdevisedawaytoovercomethis ever, itwould usually take several hourstoproducetheproblem,exceptthroughtheuseofcomplexshading desired, animated result. Therefore, broadcasters have techniques.beguntoroutinelyrelyuponvariouscomputer-aided 38Sillfurther,ithasbeenfoundthatthepriorartsys-illustration and animation systemsinordertomeettheirtemsaregenerallyincapableofproducingbothline stringent timedeadlines drawings andsolid figures. Thus, aprior artsystem will "Another area inwhich computer-aided graphic de- typically produce either solid figures orlinedrawings, signandanimation hasbeen increasingly employed, is butsuch systems canrarely produce both kinds of thatofcomputersided design. Agrowing number of40drawings. Moreover, even ifaprior artsystem can manufacturers arefinding thatthegraphic capabilities produce both solid figures andlinedrawings, prior art available through various computer graphic systems systems aregenerally incapable ofincorporating both cangreatly increase manufacturing productivity and kinds ofdrawings intothesame illustration. significantly reduce design costs. ‘Accordingly, itwould beanimprovement intheart"Asaresultofthisgrowinginterestinandneedfor48toprovideasystemandmethodforgenerating andcomputer graphics andcomputer-aided animation sys- animating graphical illustrations which minimizes the tems, anumber ofsuch systems have been developed number ofdata points which must bestored andpro- ‘hich seek tomeet theneeds ofvarious users. Typi- cessed. Itwould alsobeanimprovement intheartto cally, insuch systems, anillustration isfirstconverted provide asystem andmethod forprocessing datapoints intoanumber ofdatapoints. Importantly, itidesirable 50representing graphical illustrations which minimizes thetoobtainenoughdatapointssuchthatcurvedlinesintimerequiredforprocessing suchdatapoints.Addition-theillustration will look smooth when adjacent data ally, itwould beanimprovement inthearttoprovide a points areconnected byasmall linesegment. Itwillbe system andmethod forgenerating graphical illutra-appreciated, therefore,thatcurvedportionsofanillus- tionswhereintheillustrations remainsmoothevenafter tration will usually contain asignificant numberofdata5enlargement. Further,itwouldbeanimprovement in ppoints, Once obtained, thenumerous data points are thearttoprovide asystem andmethod forgeneratingthenstoredinsometypeofamemorydeviceWithinthegraphicalillustrations whichiscapableofrenderingsystem. bothsolidfiguresandlinedrawingswithinthesame[Next aviewing field isselected. Thedatapoints are illustration. Such asystem andmethod isdisclosed and then processed bythesystem inorder todetermine 60claimed herein Stichfeosethevewingfeldareheneliminated, BRIEFSUMMARY ANDOBJECTSOFTHE landtheillustration isthus“clipped” totheviewing INVENTION field. After this“clipping” iscompleted, adjacent data __Thepresent invention isdirected toacomputerized points areconnected byashort linesegment $0ast065graphics system which utilizes anovel system andGefinesometypeofclosed,graphicfigure.Thereafter, methodforadataprocessing pipelineusedtorapidlyeachsuchgraphic figure istypically colored orshaded process control datapoints derived from aparameter inresponse tocommands from thesystem user. The function inorder togenerate realtime animation of 4,646,075 3 4 ihpropanefoperformsreeeeithS payerDESCRIPTION OFTHEDRAWINGS tomoreefficiently achieve realtimegraphical anima- PRESENTLY PREFERRED EMBODIMENT provide adataprocessing pipeline foruseinprocessing General Discussion—Typical Pipeline Use 4,646,075 5 6predictable way.Ashereinafter morefullydescribed, Anycurvedinewhichformspartofsuchafacemayuchcontrolpointsarederivedfromparametric (orberepresentedbycontrolpointsderivedfromparamet- So-called vector-valued) functions such asBezier or ricfunctions. Forexample, fourBezier control pointsBsplineformulations canbeusedtodefinetheshapeofanycurvedlinewhich“Theprimaryfunctionstobeperformed bythenovel$formspartofsuchaface,wheresuchcontrolpointsare pipeline ofthepresent invention comprise geometric derived from thefollowing equation: {ransformation ofthecontrol data points, clipping the data points toaviewing frustum, andthen exploding ) tach curved lineorcurved surface contained inthe fo=3Patt figure soastodefine each curved lineorsurface in!0 terms ofanumber ofvery small straight line segments where orflatplanar patches which closely approximate thecurvedlineorcurvedsurface inasmooth fashion. BikOne—~*“Thedataprocessing pipelineofthe present invention ‘maybeusedwithvirtually anycomputer graphics sys-'SaretheBernstein basis(binominal distribution) func-teminwhichrealtimeanimationofobjectswhicharetionsandParetheBeziercontrolpoints.Thus,inthe‘composed ofcurved lines orcurved surfaces inadesit- example illustrated inFIG. 1A,thecurved boundaryfablefeature.Thus,thepipelineofthepresentinvention 887offace880wouldberepresented bythefourBezier‘couldbeusedinmanytypesofcomputergraphicssys-,,controlpoints886,888,890and892.Similarly,other‘temsfordifferent types ofapplications. Itshould be20parametric functions suchasthewell-known B-spline noted, therefore, that thedata processing pipelineofthefunctioncouldbeusedtogeneratesuchcontrolpoints. presentinventionisnotintendedtobelimitedtoanyAshereinafter morefullydescribed,byconfigurating Particular application ortype ofsystem. thedata processing pipeline sothatitoperates firstonForpurposesofillustrating thegeneraluseandoper-55thecontroldatapointswhenperforming thegeometricationofthedataprocessing pipelineofthepresentin-**transformations, clipping,andmappingofthegraphicvention, designated generally at200, pipeline 200 is figure tothedesired viewport, itbecomes unnecessary iiustrated inFIG. 1-as being used with computer 10manipulateallofthedatapointswhichareultimately graphics animation system. Asdepicted inFIG. 1,the used todefine thenumerous straight line segments ‘computer animation system comprises acentral pro-yywhich approximate thecurved linesinafigure. This‘cessingunit(CPU)800whichcontrolstheoperationof*°greatlyenhancesthespeedofthepipeline.theoverall system and performs various calculations Similarly, using analogous equationsandtechniques, andoperations both priortoandduringdataprocessing. curvedsurfacescanalsoberepresentedusingBezier, CPU 800could comprise awide variety ofdifferent Bespline orsimilar types ofparametric functions t0 types ofCPUs. Forexample, CPU 800could comprise 45generate control points which define surface patches.1largemainframecomputer. Alternatively, CPU800~See,forexample, thetechniques described byNewman,couldcomprise sometypeofmicroprocessor, suchas,_William M.andRobertF.Sproul,Principles ofInterac-forexample, aMotorolla 68000 microprocessor. tiveComputer Graphics atpp.309-331 (24ed.1979), CPU 800receives and transmits data tosystem users which isincorporated herein byreference. bymeans ofoneormore work stations 802. Work sta-49 "Also, inCPU 800, thecontrol points which arede-tion802maycompriseanysuitablecomputergraphic "rivedforeachgraphicfigurearecoupledwithacodeto ‘work station. Forexample, work station 802might specifically identify each particular point. This code include aconventional computer graphic tablet and indicates whether aparticular point isavertex ora stylus forcommunicating graphic information toCPU Bezier control point andalsoprovides information rela-800,Inaddition,workstation802mayalsotypically45tivetotheorderofthe points around thegraphic figure. include avideo display unit foruseinviewing the” Forexample, each point could becoupled with oneof ‘graphic illustration generated bythesystem. Further, four codes: First, Next, Bezier, orClose, Insuch case, ‘work station 802may include additional controls and- thepoints illustrated inFIG. 1Acould beencoded as /orastandardcomputer keypadforuseintransmitting follows:Point882couldbeencoded“First,”point884‘commands and/ordata10CPU800 50couldbeencoded“Next”andwouldfollowimmedi-‘inuse,work station 802is used totransmit data repre- tely after point 882inthedata stream; point 886could senting &desired graphic illustration toCPU 800. CPU also beencoded “Next” and would follow after point 800then transforms thedataintoaform which issuit- 884, point 888could beencoded “Bezier” andwould able forprocessing. Accordingly, inthecomputer ani- follow immediately after point 886, point 890could be mation system illustrated inFIG. 1,CPU 800would ssencoded “Next” and would follow immediately after transform thedata received from work station 802in point 888; andpoint 892could beencoded “Close,”thefollowingmanner. Indicatingthatpoint892isthelastcontrolpointoftheFirst, CPU 800reduces theillustration toafinite graphic figure. number ofsimple graphic figures orfaces, such as,for “Once thedata which hasbeen received from work example, face 880ofFIG. 1A.CPU 800then generates 60station 802hasbeen thus processed byCPU 800, the4relativelysmallnumberofcontrol data points which Gata representing thecontrol points ofeach graphic represent each face. - figure orfacearestored inamemory device 810.AsTForeachboundaryofanygivenfacewhichisaillustratedinFIG.1,CPU800mayadvantageously be straight line, these control points aresimply thevertices configurated soastocommunicate with either ofthreeoftheface.Thus,inthecaseofface880ofFIG.1A,65databusesadiskbus804,apipelinebus806,oraCPUControlpoints882,884,886and892wouldbegenerated busBOB.ProvidingmultiplebusesfromCPU800per-bbyCPU 800since they represent vertices correspond- mitsthesystem tofunction much more rapidly since theingtolinearedges881,883,and885. systemisnottotallydependent upononlyonedatabus. 4,646,075 7 8 Inorder tofurther enhance thespeed ofthesystem, which data wastransferred then looks toitsown input thesystem maybeprovided with aplurality ofmemory FIFO foritsnextsetofinstructions.devices810whicharecapableofswapping between the _Thedata linkages shown inFIG. 2arethose used in various data buses 804, 806, and 808. Thus, data canbe thenormal (non-diagnostic) pipeline operating modes. either stored orretrieved from memories 810bymeans $Each data linkage between thepipeline cards representsofanyofthethreedatabuses.Inaddition,adiskstorage a16-bitdatapathandaCommand bit,togetherwith‘unit$12maybeprovided toprovidegreatersystem twodatatransferhandshake lines.Inaddition,althoughstorage capacity, asneeded. notspecifically illustrated inFIG. 2,allpipeline cards Prior toprocessing thecontrol points through the areattached toaCPUminiBusfordiagnosticpurposes. restofthesystem, theusermaysendvarious commands 10Thisallows CPU 800(seeFIG. 1)totesteach pipeline from work station 802toCPU 800indicating theaction _card individually bysimulating theappropriate pipeline tobeemployed forpurposes ofchanging oranimating environment forsuch card. theillustration, One such command isacommand defin- During normal operation, commands aresent topipe-ingtheviewingfieldwhichistobeemployed when line200througheitherheadercard300ormatrixmaker‘generating theillustration. Itwillbeappreciated thatby15card201fromtheCPUbus808,Commands targetedforVarying theviewing field, theuserofthesystem may lower cards inpipeline 200are“passed through” the both modify thefield ofview and/or thesizeofthe upper cards untiltheyreach their intended destination. illustration, asdesired. Data isfedtopipeline 200through header card 300 ‘Atypical viewing field, configurated asafrustum, is from amemory 810(seeFIG. 1)which isattached to depicted inFIG. 1B.Asshown, theviewing frustum 20pipeline bus806,Below header card 300,command comprises afront plane which liesadistanceDfromthewordsanddatawordsareinterleavedineachdatalink- origin ofthecoordinate system inapositive direction age.Toprovide foreffective softerror recovery, the along theZaxis.Thisviewingplaneisbothperpendicu- commandwordsaretaggedwithaCommandbit,men- lartoandcentered about theZaxis. The viewing field tioned above, which prevents theaccidental interpreta- isalsobounded byleftandright planes, which intersect 25tionofadata word asacommand.thefrontplaneinverticallineslocatedadistance A__Additional errorprotection isprovided inpipelinefrom theZaxis, andbyupper andlower planes, which 200bymeans ofaBadFrame command. Ifanycard intersect thefront plane inhorizontal lines located a discovers something wrong, itoutputs aBadFramedistanceBfromtheZaxis. ‘command tothenextcarddown.Thecommand even-‘Oncetheappropriate instructions regarding theillus-30tuallyreachesScanConverter 820(seeFIG.1)whereittrationareprovidedtopipeline200byCPU800andthecausesaBadFrameStatusbittobeset.Thisstatusbitcontroldatapointsarestoredintheappropriate mem- advisesCPU800thatapipelinecrashhasoccurred; theorydevice 810,suchcontrol datapoints maybetrans- software ofCPU 800thenrestarts theframe construc- mitted topipeline 200forprocessing. Inpipeline 200, tion. theillustration ispositioned andoriented inthree-di- 35 ‘The normal processing sequence fortransmission mensional space byasetofgeometric transformations. through pipeline200ofcontroldatapointsrepresenting Inaddition,bysuccessive transformations ofthe control particular graphic figure (such as,forexample, figure datapoints, theillustration maybeanimated. Signifi- 880illustrated inFIG. 1A),isasfollows: cantly, during such animation, theillustration canbe First, matrix commandsarethensenttomatrixmaker transformeddifferentlyforeachvideoframe,givingthe40card201.Thesecommandscauseconventional 4x4 appearance ofsmooth motion. Thegeometric transfor- transformation matrices tobequickly assembled with mations performed bypipeline 200include rotation, hardware sineandcosine lookups inmatrix maker card translation, scaling (i.enlarging ordiminishing size), 201.Aseach matrix isassembled, itisfedtomatrix ‘andshear (tilt). Other geometric operations performed multiplier card202where itisconcatenated intoacur- bypipeline200areclipping,perspective,hiddensurface45renttransformation matrix.Matrixmultiplier202can rejection, shading, anddynamic curve processing, Fur- save andrecover thecurrent transformation matrices ther, pipeline 200performs preliminary phases ofthe onamatrix stack which iscapable ofholding 64matri- scan conversion process and supplies synchronized ces. graphic color information totheframe buffer 830. ‘Next, aNewMatrix command issenttovector multi- ‘After processing bypipeline 200,thedatapoints are$0plier card 203.This command causes theappropriate sentintheappropriate sequence intoscanconverter 820 current transformation matrix tobedownloaded from ‘where theillustration istranslated intovideo scan lines. matrix multiplier card 202into vector multiplier card Thedata isthen passed through frame buffer 830and 203.This transformation matrix determines thescaling video output 840toavideo display unit850fordisplay. andorientation inspace which wilbeassumed bythe 55nextgraphic figures tobeprocessed bypipeline 200. GeneralPipeline Operation Inaddition totheforegoing, when thegraphic figures ‘Ageneral block diagram ofpipeline 200isshown in tobeprocessed bypipeline 200represent thefaces of FIG. 2.Each boxrepresents oneprinted circuit card solid 3Dobjects, aspecial preprocessing phase alsowhichcontains@particular blockofhardware con-occurs.Duringthispreprocessing phase,afilecontain-trolled byaseparate microprocessor, ‘ashereinafter 60ingthenormal vectorofeachfaceisinputintopipeline ‘morefullydescribed.Eachblockofhardwareperforms 200throughheadercard300.Thesenormalvectorsare fdifferent function. Except asotherwise noted, each then transformed bythecurrent transformation matrixcardhasaFIFO(First-InFirst-Out) onitsprimary invectormultiplier card203,andthetransformed vecinput tobuffer thedataflowthrough pipeline 200and __torsarethendiverted toshader card204. thereby maximize datathroughput, Thus, when apar-65 Shader card 204examines each transformed normal ticular card hasfinished itsspecialized computing task, vector andsetsaFace Visible bittozero ifthefaceis theresults aredelivered asynchronously totheinput “back-facing.” Shader card204alsocompares thenor- FIFO ofthenextpipeline cardinline.Thecardfrom malvectors withapre-stored lighting source direction 4,646,075 9 10 inorder tocompute anappropriate shade fraction for andmatrix multiplier card 202canbeused togeneratetheface.Theseshadefractions may,forexample, bethetransformation matrixforthenextgraphic figure.ItComputed based upon asimple “Lambert's Law" light- willbe readily appreciated thatthisarchitecture greatlyingmodel increasestheprocessing speedofpipeline200,andfur-‘After thenormal vectors aretransformed byshader $ther aids inachieving real time animation card 204, theFace Visible bitsarethen sent back to FIG. 2also depicts astatus line215connecting ex- header card 300. Header card 300then sends theFace _ploder card 211toCPU Bus808. The exploder cardVisiblebistacktoCPU800seeFIG:10thatthestatusine218suedduringanoperationcalleda"Ves system software can render the faces correctly with torHitTest." This operation allows asystem user torespecttohiddensurfaces.Thus,pipeline200andscan10knowwhenheorsheispointingwiththestylusoftheconverter820aresavedfromhavingtoprocesssuchworkstationdatatablettoavertexoredgeofaparticu-invisible faces. largraphic figure. The“Hit Test” operation isused toTheshadefractionscomputedbyshadercard204areselectadisplayofelementsforvariouseditingfunc-sent toandstored insean converter 820. These shade tions. Fractions aresubsequently used toscale down the15 “When illustration complexity increases sufficiently, brightness ofeachofthefaces totheextent thatsvch pipeline 200cannolonger process allthecontrol data facesfaceaway from thepre-stored lighting source Points ofanillustration rapidly enough togeneratedicection. ‘real-time animation. However, ananimation canstillbeAfter completion oftheabove steps, including any displayed inreal-time iftheanimation isprecompiled. needed preprocessing, control data points representing 20Dy : Honoe570 ssenting2°Duringsuchprecompilation, pipeline200operaicsa5 thenextgraphicfigurestobeprocessedbypipeline usualexceptthattheCPUoutput213ofviewportcard aretransmitted through pipeline bus806toheader card 49isusedtodivert theprocessed dataP is P pointstodisk 4300,Each control point isthenpassed ontovector 19(seFIG. I),Thess afer theanimation iscom‘multiplier card 203where itistransformed bythecur- La Then,ip!nsfc 7pletelycompiled, itmaybedisplayed inrealtimeby renttransformation matrix. transmitting thecompiled datatoheadercard300using ‘Aftereachcontrolpointisthustransformed,itisWansmitiogthdatatoheadercard300using passedontoaseriesofclippers208-209whichremove§,DiectScancommand,Thesonradassotisainvisible portions ofthegraphic figure,ie,thosepor- assed throu cardsthedatareaches exploder card211,where thedatais tionsoftheigurewhich heoutside theviewing frstum {6 Se a eeerea compileillustrated inFIG.1B. 30 Processed Suck -Thethree-dimensional, transformed, clippedcontrol 19?pontoiELapnipr pesteretcome, pointsarethenpassed toviewport card210,There, the Honcomplexity, ThecostofcompitaionControl pointsareprojected incorrect perspective onto i rage:2two-dimensional viewingsurface(thewindow)andParticularConfiguration andOperationoftheVariousarethenmapped toadesired areaonthevideo monitor 38 Pipeline Cards (the viewport),Significant,uptothispointinpipeline200,anyheindividualcardsinpiping200mayhavety ‘curves havebeenrepresented asan ordered listoffour SU aration which is istentwit gen cpsbecoalaperaectedPefenspent a ve.However, whyesefourcontrolpointsare40skilledinthear ay ,1¢varioustransmitedtoexplodercard211exploer'card211Pipelinecardsmayhaveanumberofdiferentconf “explodes”suchcontrolpointsintonumerousdatasions:ma)awidevariet‘ficcircuit pointswhlchthendefine2largeumberofsmallcomponentswithoutoonotLioonneecha Straight linesegments (edges) withsufficient resolution acteristics andoperation of pipeline setfortoapproximate eachcurveinaverysmoothfasion,45above.Therefore,thfollowingmoredealeddessrip-regardlessofthesizeoftheviewingscreen.Thus,un-tionofthevariouspipline cardsinpipeline 200smerelyikethepriorarttypesystems, thesystemandmethod ustratve ofonepresently preferedembodiment usedinthepipelineofthepresentinventiondoesnotachofthepipeline cardsineproceseatofhedatapointssedtoactualydefineASustedinFIG.2,ppeine200lnchudes13 thestraight linesegments which approximate acurve, $0indivi s201-7 Because thefunctionbutonlythsepointswhichservewsthecontrolpoints,andmethodofoperationofmosofthecardsissome- The system andmethod ofthis invention thus provide a What similar, itwould greatly reduce manufacturingwasowertul typeofproceeing forigureswhichareandassembly costsifthevariouspipeline cardscouldbeComposed ofcurved linesandsurfaces, which hashere- configurated identically. Accordingly, twelve ofthetoforenotbeenavailable intheart. 55pipeline cards(cards201-212) canbeconfigurated withFinally,theedgesofeachgraphicfigurearepassedtoidentical printedcircuitboardswithminormodifica~incremental formcard212which recodes themintoationsastowhich circuit components areusedoncach formatappropriate forscanlineconversion. In.addition, printedcircuitboard.Thus,pipelinecards201-212can ‘whenpipeline200isoperatinginso-called“Vector bemanufactured andassembledusingasinglebasicMode,” incremental formcard212converts eachedge60card.Pipeline card300,ontheotherhand,inotreadily intoathinrectangle(fouredges)suchthatthegraphic adaptable tothesamebasicconfiguration ascardsfigureitendered ontheviewing srettwouldbe201-212 ndmostherefore, beconfiguated somewhatfon linedrawing. Then, therecoded edges aretrans- differently.mittedtoscanconverter820. Tnviewoftheforegoing, itordertosimplifythe‘Importantly itshouldbenotedthatthevariouscards65followingdiscussion,thebasicpipelinecardwillfirstbe inpipeline200operateindependently fromoneanother. described,illustrating theoptionalcircuitcomponents‘Thus,whilethecontolpointsofonegraphicfigurearethatcanbeusedonthecard.Then,eachofthepipelinebeing sent down pipeline 200, matrix maker card 201 cardsinpipeline200willbedescribedindividually with 4,646,075 iW 2referencetothebasicpipelinecard,withappropriate _Alternatively, datamaybefirstinputthroughdriver‘modifications thereto being pointed Out 246into either XRAM 244orYRAM 238. Such data ‘A.Basic Pipeline Card ‘may then bedriven totheappropriate input ofmulti- The basic pipeline card isillustrated inthegeneral plier 248, asneeded. Forexample, XRAM 244andYblockdiagramofFIG.3.Thebasicpipelinecardisa$RAM238maybeusedtostorematricestobemultipliedspecial purpose, bitslice, micro-programmed processor bymultiplier 248. Inaddition, theposition oftransceiv- Used invaFious pipeline positions toperform several ers240and242permits data stored inRAMs 238and high speed data manipulations (such as,forexample, 244tobedrivenbacktodatabus237,asneeded rotations, clipping, perspective, andlighting), The basic Finally, multiplier 248may also receive data atitsY Pipeline card isspecifically programmed ineach ofthe10input from constant PROM 254, ashereinafter more Several pipeline positions toexecute special algorithms fully explained. designed togenerate thedesired graphic functions. The basic pipeline card may also include anin-line Referring now more particularly toFIG. 3,com- transparent latch 280. Insome cases, itmay befound ‘mands areinput tothepipeline cardonbus235.Such thattheset-up timeofALU 234requires thatdatabecommands arestoredinmappingPROM222,anda15tatchedondatabus238.However,if'itifoundthatthe portionofeachcommand maybelatchedincommand set-uptimeforALU234issufficiently shortlatch250 atch220forrouting tovarious circuitcomponents. taynotbeneeded. Eachcommand isnexttransmitted tosequencer 224.An "Thebasicpipeline cardalsoincludes afullshifter 252.illustrative example ofthecommands usedtoprogram Fullshifter 282isusedtoshiftdataagiven number ofPROM222issetforthinAppendix P. 20bitstoeithertherightortheleft.Thus,datainputtofull pregueneer 224thencommunicates withmicro-code shifer252bydatabus257maybeshiftedtotheleftfour iandbetel inordertointerpet en withtheshiftedoutputbeingtransmitted todata mandwhichhasbeenreceived.MicrocodePROMs230pissith patbeing then transmit theappropriate information tonextad PUEZSS hint data toeitherth ypically,ashiftercircuitmayshiftdatatoeitherthe dresscontol 226andsequencer224toenablethe83%251ortheright.ThusinordertoincreasetheVersat- temtoexecutethecommand.Inexecuting theCOm-ityofsuchashifter,theshiftermaybeusedinconjunc: mand,sequencer 224mayobtainthenextaddresFOionwitheater236.ASSuming,therefore,thashifter eithermapPROM222,nextaddresscontrol226,oF259iscapableofshiftingdataonlytotheleft,arightmicrocode PROMSandlatches230.9 aftmayeaccomplishedinthefollowingmanner. Microcode PROM: 230arealtousedtostoragecon-30Dat,Tetcwistedfromdatabis235throughtwister stanswhichareneededformathematica computations 336togatabus237.Thedatasthenshiftedtotheleft bythepipelinecardThunconsiantmuiplser 2928 yereuized numberofis.Theouputofshite283scontodatabus235.Constant multiplexer 232ialsoused {heagainstpesJinwwister236.TheSalcutee totransmitvariousparameters toothersystemcompo-35performed. islnents 7 wesaclock pulsewhich is Thebasic pipeline cardfurther comprises aconstantsFnreereeensHoeecervariusPROM284.ConstantsPROM254isusedfocomputeerat mnthelinecards sinesandcosinesandtododivisions, usingalook-upOOErt Te eeeAccocd.40method.AddressesmaybeinputtoconstantsPROMeensClockcontrol228's providedonthebasicpipe. 254fomeitherdatabus235through latch286orfromteeatoallowthecardsoveletimetovaried,asdatabus237throughsine/cosine input258.Anillustra-" tiveexample ofthedivision andsine/cosine constants necessary.Turingnowtothedatamanipulating componentsofwhicharcprogrammed intoconstantsPROM254set eee oanmeaofthecardandtransmittedfromconstantsPROM2540the¥inputof itregulatesthevariousdatacalculationsandmanipula-_mulplier 248,Suchdatamaythenbeusedbymultipliertionsperformedbythecard,Ingeneral,databus238is,marequiredcomputationoraleratvely thedat sedfoInputdataintoALU234,whiledatabus237iss0maybedventodataus237throughranserves24 usedtotransmitdatafromALU234. inaddition, icpipelinecardalsoincludes etnthes component ofthebasepipeline cardisslack260.Dataiswritenintothestack260frombustwister 236.Twister 236isusedtotwist datafrom bus 237through driver 262.Data maythenbereadfrom235tobus237bytakingbus235’smostsignificantbitstack260throughdriver264ontodatabus25andputingtontobus297sleastsignificantbitwithall$5Als,a8depictedinFIG.3,thebasicpipelinecard ftherbitsbeingsimilarly inverted (ortwisted) from includes #data a PROM246may aE ect inconcardopeatiog.Anilusraveexampleofthecon. twister236mightbeusedarediscussed belowincon-cardoperations.Anillustrative exampleofthecon-nectionwithfllshifter252 sich aefordindtaPROM266th in"The basic pipeline card alsocomprises amultiplier 60 Appendix ;248,havingothananda¥inputMalini248sThevariousinputsandutpothebasicpipeline ‘sedtoperformmultiplication onthedatatransmitted cardareasfollows.TheprimaryinputcomprisestoilsrespectiveXandYinput. first-infistout(FIFO)274.ByusingFIFO274a53 Various circuit components areprovided totransmit primary input, several commands orparameters maybe theneeded datatotheappropriate input ofmultiplier 65sequentially transmitted tothebasic pipeline cardwhile 248. Forexample, transceivers240and242areprovided thepipelinecardcompletesalengthyoperation.Thus, tocenablethedirecttransferofdata from data bus2370 data flow through thepipeline card ismaximized. A theappropriate input ofmultiplier 248 primary input handshake 272isalsoprovided toassure B 4,646,075 1“thatdataisnottransmited tothebasicpiplinecardnumeralsprecededbytheletters“R”and“C,"respec-throughFIFO274untlFIFO274sreadyforthedata,tively.Varioustestpointsontheschematicdiagrams"Thebasi pipeline card further inciodesu secondary aredesignated bynumerals preceded bytheleters input atch 266,When's secondary input tothe cards “TP. Also, switches aredesignated bynumerals pre- needed, datamaybetransmitted tothesecondary input $ceded bytheletter “S,” andindicators aredesignated Imch 268andthereafter tansitted(o data bus273, A. bynumerals preceded bytheeters "DS." ‘ccondary input handshake 270isalsoprovided (0a%- The specific circuit components which areused inseotharlatds notranamiiedtoseconsaryinputlatchaccordancewihthispreferredembodiment ofthebasic268untillatch268isreadyfordata. PipelinecardareidentifiedinTable1below.Thoseinaddition tothe primary andsecondary inputs, the10Sled inthe atwill,however, realy appreciate that tasic pipeline card canalsoreceive data from CPU 800 wide variety ofdifferent specific circuit components (ce BIG. 1).This isaccomplished inthefollowing ould alsesroauce socepable results Sciner Fit, theCPU sends anaddress toport de: Referring now 0FIGS, 3tnd3A,commands are Codes 388Iftheaddres received isthe correct addvess eter’ onbus298to:Mapping Prom 222(U109) and eethcparticular card, thebai pipeline card ilThe aeneeaeanePtofthecommand fcc dt commands fomCPOfO0‘how hethsbycommen ch20(U910bevoted transceiver 254.a several places, withtwobitsbeingsenttocondition ‘Whentamsmiting tothebasicpipelinecard,theSwern 1bitsbeingsenttoconditioncoetrermnmins ote iept che une,OLwdUT,wihaedee transferred isaparameter otacommand bymanipulat= 20 -omprises integrated circuit (IC™ waterediparamefacommandbyarial,2_Segencet224comprisitgatedcitIC”) a sequencers, UI2I, UIS0, and UI96. In.addition, se. maythenbetfansmtied todatabus235through input (Quencer 224inclades ICmultiples Utz2 andUI1LGataport260,CPU800mayalsotransmitcommand or280,CPUS00mayasotansmitacommand'e SORgatesUNOA-Dwhichallowmodieation ofcontrolport278whichcamstbapipelineAFheagdrssreceivedbysequencersUIA,UIS,and easeeone seceive datafromthebasicpipe. U#36depending upontheparticular command beingtueculed ordepending uponthefieldsinsuchcome lingcardthroughtransceiver264,First,CPU800'may ©xeewtedoFdependinguponthefedsinsuchcom. eadvarius bitsatstatusport282todetermine the . the combieadvarious erm taybeusedtomodifytheaddress. Statusofcertainoperationsandfunctionsofthebanc™Y,DeWiedtomodiytheaddressSiplnecard:Inaon,datamaybetansmiedto20_NEWadresscomrol226compris»FROMU120- CFU" dn oathoprdeotRS oe seoicose and transceiverransceives 4cardaloincl felectionofthenextSourceofaddres:1wobitscontrol Ahohate wie crao aes©otfaceCinCisandUnesoe ayetebeisistheprincipaloutput>bitscontrolwhetherthenextaddressisreceivedfrom aut ntsbetween din pine20Ge16,2) BSCote wheehe receivedfi primaryoutputhandshake isalsoprovi to next weesSt microcode or‘helre thatdatas notransmited toanother cardinthe (FUMapping PROM U109orfromtheinternal sepipelineuntilthatcardisreadyfordata. quencerstack,msicroprosram bananaholdingree ‘Finally,thebasicpipelinecardisalsoprovidedwith Inaddition,nextaddresscont includescondi-3eta27Inesowasnanaromaonmallee,IZandUIIpacon ‘system,reset276causesthebasicpipelinecardto|ionsyencersU121,U150, example initialized byresetting various circuit components and OFthedataprogrammed,intePROM1200fnextaddress neers control226 imAppendixS. Pfeterenceinexmade(0FIGS,34-31,whichillsFinalFIG,34ahetrlclockcontrol tratein'moredetailonepreferedembodiment ofa45cfu cpipelinecard.Thecycletimedetailedelectrical schematic diagramderivedfromthe_thebasicpipelinecardisnormally 100nanoseconds.blockdiagramofFIG.3,ThoseofordinaryskillintheHowever, therearesomeoperationswhichtakelonger. artwill,ofcourse, appreciate thatvarious modifications For‘example, thecycle timeformultiplier 248is140Wofedetailed schematic diagrams ofFIGS. 3A-31 may nanoseconds. Therefore, inorder tolengthen thecyclebeslymadewithoutdepartingfromthesacl0Sn fohsfedackfom:MicoondeCharacteristics of the invention. Thus,thefollowing providedwisfromMic Guertin ofthedetailed schematic diggrams ofFIGS. PROMS230toallowselectionofoneoffourcardcycle Sa-3l'smendedonlyasanexample,andsimplyilus-times:100,150,200or250nanosecondsaaeeeaeree onefedcabedinent Thevariows Clock control 228alsoprovides forstopping the circuit stages corresponding toeachofthefunctional 55clocktothecardincertaincircumstances. Asdiscussed flocks otBic 9aroutlined inFIGS 3A‘31 bybold, above, thebasic pipeline cardreceives commands fromGhohedlinesndarenumberedwithlikenumerals. eithertheCPUorthePipelinebuses,Themicrocode“Sch dagn 3hSfae eadooneother Progammingovieppinecarhenhead y’meansofthevariowsconnection points1-130lo! commandwhichhasbenCieedlongthesidesofeachfigure.Tuconsidering the60‘TheclockcontrolcircuitryilustratedinFIG.3issetStialed schematic diagrams ofFIGS3Ac31heefore, upsowhenacomand ipsatiated, theclockcei points havang lkenumerals should becos: willstop after100nanoseconds andwaitunlacondi- SGered mebling slectialy connected soastoprovide thonBitfst signifying thatthe command iseady for saryeta tacts between thecircuit components flux. input When thecommand isready, clock control 228 trated inthe several Figures, 65starts thecycle clock again. Thecard clock isalso Tnaddition, throughout FIGS. 3A-31, integrated "stopped when anticipating «datainput tothecard's circuits arerepresented byanumeral preceded bYthe primary orsecondary input. However, ontheCPU [eter "U" Resistors andCapacitors aredesignated by Interface, ifdatainput not avaiable, thecardsoftware 4,646,075 15 16 willloopbackuntilthedataisavailable instead ofstop- words. Themost-significant dataword isoutput tobuspingthecycleclock 238,Suchwordisoutputintheformofasignbitanda‘Theclock control operation isgenerally thesame for fractional 2'scomplement number.thecardoutputs,Afterthecardperformsonecommand ‘Theinputstomultiplexer 248,designated inputsXandcomputes thevalues needed, itsends theoutput to$andY(seeFIG. 3),areeach connected toa16x16theneatpipelinecard.However, ifthennextcardisnotscratchpad RAM.YRAM238comprises RAMsU7,ready forthedatatobeloaded, clock control 228will U6,U23, andU22; XRAM 244comprises RAMs U2, stopthecycle clock untildataoutput canbecompleted. U1,U18andU19. Inaddition, transceivers 240and242 ‘Clock circuit 228 also generates Write pulses for comprise transceivers U21&USandU20&U3,respec- stack260andtheXandYRAMs244and238.Impor-10tively. tantly,ifaWritepulseisbeinggeneratedbymorethanThereisonlyonepipelinecardinthesystemwhich conedeviceatthesametime,andaninstructionstopsthewillhavebothXRAM238andYRAM244:matrix clock when acondition isn't met, allWrite pulses will multiplier card 202. The useofboth RAMs allows stor- finish andnotbedelayed byclock stoppage. ageofthecurrent transformation matrix inoneRAM ‘With reference toFIGS. 3and 3B, microcode 1Sand thenew matrix tobeconcatenated intheother PROMS andlatches 230comprise PROMs U142-U149_- RAM, thereby decreasing thecycle time forinput of and U1S1-U153 and theassociated latches U128-135 thetwo values tomultiplier 248. Thus, themultipli-‘andU137-139. Thelatchesarealltiedoutputenabled _candsfortheXandYinputstomultiplier 248aretaken‘except forU132, whichisthenextaddresslatch.Sincesimultaneously outoftheirrespectiveRAMs,and thenext address may come from themapping PROM 20loaded andmultiplied insequential clock cycles.222‘insteadofPROMsU142-U149 andUISI-U153,_ Inordertoloadconstants intoeitherXRAM244orfoneoftheother latch isenabled, butnotboth. YRAM 238from bus237, there isonly oneinverting "Asfurther illustrated inFIG. 3B, constant multi- driver 246(comprising drivers U48 andU43). Drivers plexer 232comprises multiplexers UII7, U106, UI18___U48 andU43areoctal inverters andareusedonthe‘andU107.SixteenbitsfromPROMsU142-U149 and25inputsofthe scratchpad RAM's inorder tocompensate UIS1-U153 maybeentered through themultiplexers fortheRAM chips, which inherently invert their out- andputonto bus235. Allofthese bitsaredual usage put.(thatis,theyarenormallyusedforsomething else),but__In-linelatch250(comprising transparent latchesU4Sthebitscanbeusedtobringaconstantontobus235,ifandU46)isalsodepictedinFIG.3D.Thislatchis needed.30required because ofthe51nanosecond setup time of ‘Theremaining decoders U119 andU108 shown in ALU 234.Inmost cases, acycle timeof100nanosec- FIG. 3Bareused todetermine what drives buses 235 _onds would give only 49nanoseconds togettheresultand237(undercontrolofthemicrobits). Thus,moreontobus235tomeettheALU234setuptime.Inmanythanonedevice isprevented from driving abusatany cases, thisisnotpractical. Hence, transparent latches ziven time. 35.U4SandU46areinserted inbus238atthispoint. Data Referring nowtoFIG. 3C,ALU 234comprises bit- may, however, bedriven through latches U4SandU46sliceprocessors U79-U82, ALU234alsoincludes ain“Transparent Mode”ifthesetuptimeisadequate. IfLook-Ahead Carry Generator U83connected toall thesetup timeisinadequate, however, thedatacanbe fourslices latched attheendofthe100nanosecond cycle, thereby ‘Two condition bitsareused from ALU 234; zero (0)40allowing thehardware toperform some other task. On. ‘andnegative (—).These twocondition bitsarelatched _thenextcycle, thedataisbrought from latches U4Sand.inlatchU108becauseofthetimerequiredtogettheU6intoALU234.Sincebus235hasonlytwodevicesresultoutofALU234andsenseitthroughcondition drivingitontheleftsideoftransparent latch250(eithermultiplexers U112 andU123 (seeFIG. 3A).Thebitsare latch 280ormultiplier 248), onlyonemicrobit andan latched ona100nanosecond cycle andasecond 15045inverter U84D areused forcontrolsoastoallowonly nanosecond cycle isused forsensing. Onthesame sense onedevice todrive bus235atatime. tycle, theprocessor continues with anormal pathorthe Shifter 252isillustrated inFIG. 3E.With referencepathmostlikelytobecorrectandstartsthatoperation _toFIGS.3and3E,shifter252comprises IC'sU97,U87,while thebitsarechecked. Ifthecondition turns outto U61, US1, U96, U86, U9S, andU8S andisconfigurated bewrong, thepathisswitched andnotimewillbelost.$0asabarrel shifter forleft-shifting upto16places inone Ifthepathchosen isthecorrect path,thecardwillbe clock cycle. Priority encoders U69andU70,together ‘onecyele intothecomputation required andwillnot withinverters US9andU60areusedtodetermine the hhave lostanytimewhen thecondition ismatched. correct amount ofshiftsoastoputtheoutput inthe ‘Two other condition bitsarelaiched onthebasic form OIXXXXXXXXXXXXXX. The encoded infor- pipeline card, theInput Data PortReady withData and$5mation isthen putintotheshifter sothedatacanbe Output Data PortReady forData. Actually, these are shifted bytheproper amount. Latch US2allows capturebitsinstatusport282,buttheyaresensedbylatchU10S _oftheencodedshiftinformation andmultiplexer U72becausetheyhavetobeinputtocondition multiplexers dictatesthechoiceofeitheranewshiftencodeoranforconvenience incommunicating with theCPU 800 arbitrary amount ofshiftlatched intolatch U62. The (seeFIG. 1).These bitsareentered intolatch U10S in60amount ofshiftfrom either ofthese latches canalsobe ‘ordertosynchronize themwiththecardclockcycle. drivenbackontobus235forinputtoALU234,ifAnother circuit shown inFIG. 3C istwister 236 needed.(comprising US4andUS7).Asexplained above,twister Whenshiftingleft,zero-fillisused.Thatis,insteadof236isused totwist data from bus235tobus237; andit rotating thebits, thevacated bitsarefilled with zeros. ‘cooperates withshifter 252toproduce arightshift. 65Foraright shift, there maybesome cases forusing a Referring nowtoFIGS. 3and3D,multiplexer 248 sign-fll instead ofzero-fill. Thisfunction iscontrolled (Us)performs afunctional 2'scomplement 16X16 bit byasinemicrobit which isattached toAND gate multiply with a32-bit result, output astwo16-bit data U88D. 4,646,075 17 18 FIG. 3Ealso illustrates PROM 264, Itch 256, and used inconnection with status port 282todeterminesine/cosine input288.Asshown,PROM254comprises whetherstack260isetherfullorempty.CPU800 PROMsU3andU24,latch286compriseslatchUSOreadsstatusport282todeterminethesatusofvarious tnd sine/cosine input 288comprises driver UA8. In card functionsdition,aninverterUSACisprovidedtoinsurethat$Thecardresetcircuit276salsodepictedinFIG.3H.bothlatchUSOanddriverUd9cannotdrivePROMs—Therearethreetypesofcardresets:power-upreset;U34andU24atthesametime controlportreset(romCPU800),andpipelineitate.FIG. 3Fillustrates theconfiguration ofstack 260. Receipt ofthese signals byreset cicuit 276will causeReferringtoFIGS.3and3F,stack260comprisesstackvariouscardcomponents andfunctionstobeinitializedICsUtandUZ7.StackpointercountersU63,USBand10and/ortested.Inaddition,resetflip-flopUSIAalso U37 arearranged intwo separate sections. One, U3T7, is servestoprovidestatusdatatoCPU800onwhetherthe 2stack poner. The others, USS andUS3, comprise a Power-on Confidence ‘Tes, mentioned. above, “was frame pointer which ischosentomakeaI6-wordframe.passed. Every’ time acomplete frame isstored, theframe "Finally, FIG. 3Halsoillustrates input data port280. counter (U59 andU68) willincrement tothe next frame. 1SAsshows, input data port 280comprises latches USS Data iswritten tothestack from bus237through driv- andU67, together with associated control components. crsU10 and U9;and data isread outfrom thestack on "Normally, thepipeline cards only look forinput frombus235throughdriversU28andUI2. primaryinput274.Thus,ifdataistobesenttothecard‘Asfurther depicted inFIG. 3F,data PROM 266 from CPU 800, CPU 800must firstsend acommand to comprises PROM:U26andU2S.PROMsU26andU2520thepipelinecardinputport.Suchcommandallows areused tostore data associated with theoperation of selection ofasourceofcommands forthecardtoexe- incrementalformcard212,whichisdescribedinmoreutewhethernormal(fromprimaryinput274)orCPU. detailbelow. ‘ThesamecommandcandirectthecardoutputtoeitherFIG. 3Faioillustrates thesingle-register secondary primary output 292ortotheCPU output (transceiver input latch268andtheassociatedhandshake270.Hand-25344)"Thecardwillsayitheselectedinputofoutput shake 270signals when theinput isready fordata or ‘mode until itreceives anew command from CPU 800. when there new data available fortheinput Hand- "PGS3 and’alshow thepipeline card address de- Shake270strobesdatabetweenpipelinecardssuchthatcoljecircuit488.Eachcardhasaseparateaddress new data cannot beinput before theolddata hasbeen hen CPU 800addresses thecard, aDTACK. signal femoved from latches U38 andU36. 20249isreturned toacknowledge receipt ofthe address Reference isnowmade toFIGS. 3and3Gwhich *@ypy aetransceiver 284comprises. transceivers ilustrate primary input FIFO 274and itsassociated 416 andU11S. Such transceivers areused tocontrolhandshake272Brimaryinput274comprisesaIG-word—Guracdrven onteffofthecardfromCPUBes808,TheFIFO(UI7,U82,Ul6andUal),Forthe17-bitdataGuaSrvenenoropeltiecorttiledbytheANDingStructure, decried above, eachchipis16words deep 35Gnesye Oe so asgAas Address Decode bySbitswide. Theinput datahold timeforthe FIFOs (E°\hwyteetreyUierDevaStrobeThenormaldies: 10nanoseconds patdataachesUBSandUS2teSomeRowromtheCPUbsthecardFequiredtomeettheholdtimeandallowfullspe 0Teo eeeerunnatdateoproonLachUMidandtheptbeat'sdotaieA.TeourFor ‘areclockedbyaninputstatemachine,xshown.402868°62 eeeeeCupinchesUSYandUSTaeabopve,andgmp ebUIOEWHOSnd Pethey allow outputasfstaspossiblefromtheFIFOwit singtoTable1below,thevariousintegratedoe er Thewanle Refers,10Tale|telow,thevariousingrid dataattheFIFOoutputisstrobedintooutputlatches Ghwrstions ofFIGS.34-31aresetforth,Thecompo. Us8andUB7,andthesamestrobeisusedtostrobethe4sHustation ofFIGS,3areee eteFIFOeupatcockfora100nanosecond cycleA‘Figure Restor refwaett andestance shown,astatemachine(handshakecircuitisusedfor .Resistorsere4wattresistorsandresibothFIFOinputandoutput. statedinohms.Capacitance isstatedinpicofarads.Referring nowtoFIGS. 3and3H,control port278is TABLE 1instrated. CPU800(seeFIG.1)writescontrolinfor.$0"Great CompuoftheBaPpsCord‘mationintocontrolport278.Suchinformation com-= rege Cucaprisesthreecontrolbts:oneisaresetbt;thesecondis notmentSessE'command bit(the17thbitineofthedatabuswhich—§S29 —_differentiates between commands andparameters), and u ca thethird isused byCPU 800 toturn onLED DS2._ $5 % fetsses“ThereaethreeLEDsonthebasicpipelinecardtwo us Meviawgreenandonered.OnegreenLEDDSIisturnedonby te nethecard when thePower-on Confidence Test ispassed ue ad ‘That is,LED DS islitafter thecard successflly exe- o Bautesanumberofroutine integrity tests. LED DS2 is60 ve fru turned onbyCPU800afterallpipeline cards aretested Ulo aforsuccessful completion oftheintegrity testsAthird on ania LED (DS8) isturned onbythecard when input FIFO th nee Adis fll. Ths, LED DSS indicates thecard's backing tie sits upthepipelineandthepreviouspipelinecardisholding65 ue weitsoutputdatawaitingforstorage. bie susFIG. 3Halso depicts status port 282, which com- oh 3B prises IC'sU78andU77, Stack sensors US6andU80 are us aris 4,646,075 19 20 TABLE 1-continued TABLE l-continued Great ComponentsofheBasicPipelineCard Grr Componens oftheBusePeteGaréSOtar MaLsias 5 bin ar vn at bins arseret] FES vine aes um ns20 vies EISas ns vide itdv2 ns vier Arasor 01490 ios TFI38 ux TARR 0 vie Dsieus at unio ax0 aro un MFIs un eH ui F251un ars uns arn us rie ute fare ve 73 is uns TaLsetstuss aE bite ALASv3e arse oi jars?us Tart oi ara?uss F108 vn are us iat 120 sistwo HES 20 unt Buava 74525 um Sarisua 2482s ui arastus ar260 une jureva araes uns haeus ai vine eanvas AFT s vin ars. un ara vis arsroy Jar360 uns Faba ara vio arinv0 fare unt Jarsust TAPS vin AES05 ar 0 uns aravs FI vise arsevst sina uns arse Uss are une BIA, Us aeS2t unt jarsus aes vis arsevss irae uns jarsvs 4Fa0 38 vio 74Lsi23ue eras via atUst F350 vie nseve, TAF3I6 vis sis Us) arias ia saese aro bus Hiseves aro ry ou nsvee 5atsoe vie nse ver arse une sisbes aes uN saeves ates iso BIA bio ries vist rsun ares “ vin sie un aras7 us, Psie un ses vis siiUm 1400 vis furorurs 408 vise ritue 74F20 a7 fara Aes ue wee 0 No Resianceup 2018 oaon 29018 m 10kust 25018 RS 10k ve orb Re 108un erie RS 10K ve Jar 5s Re 2Kuss F350 RT 0vas 14F380 Re 2Kus F350 RS 0us aro R10 50 ws a Rul 2K,030 farts 0.oo —=vr 7AS40 ‘Sanson,bs sara No. Copaciance 053 arse _— ,.--O,94 74F08 —ss AF3S0 se urs 65Eachofthespecificcardsinpipeline200willnowbeun up discussed. Insuchdiscussion, reference willbemadetous Sees thedetailed description ofthebasic pipeline cardsetvic0 F382 forthabove,asappropriate. 21 4,646,075 2 3B,Matrit Maker Card then stored inXRAM 244andbecomes thenew cur- Matrn mater card 201hasthegeneral configuration rentsansformation matrix ofthetae pipeline cardOfFIG'3 However: mara Also, matrix muliper card 202includes stack 260. ce easJOPdocssotleds thefellowing compo: Stack 260isused tostore frames consisting ofentire ons: winter 236% RAM 244, shifter 252 stack 260, 5maties ataPROM 266,secondary output latch268,secondary _Itisapparent thatthecomponents which formmatrix. oe Ma TOFICO aotprimay input multiplier card202could beprogrammed wsing anyfandshake 272, Suitable technique toaccomplish thefunctions de- dst 7 yove, themain purpose ofmatrix seribed above. Anexampleofonesuitableetofmicro maker card201istoquickly generate transformation 10codeinstructions which maybeusedtoprogrammatrix,matrices andoutput themtomatrix multiplier card202. ‘multiplier card202issetforthinAppendixC.Appendix ‘Themaintaskofmatrixmakercard201increating such illustrates abitdescription mapwhichreferencesInniroes thecomputadom ofsinesand cosines tote-bit exchlineofthe microcodeofAppendixCtothepartic. atesthecom oeaaealnate__lrfeationnthemicrocodePROMSU142-U149and Mey, ordetenmine which matices areformed. 'SUISI-UIS3 (GeeFIG.38)atwhich themicrocode i ‘Sincematrix maker card201hasnootherpipeline cards ‘stored. Thus,inordertomakeandusematrix multiplieraboveit,allcommands arereceived bythiscardfrom ‘card202inaccordance withthepresently preferredaboveall codes feretnnn gewednlous AORhymarinmakercard20include:_.cometthematrix mullerICssingthepinconnec Matricesformedbymatrixmakercard201include:9{ontshowninFIG.3b,andthenencodethePROM rotationmatric,traslatonmaticsscalingmatrices, ic5MTe2-UI49 andUISL-UIS9 using themicrocode of td titmatrices Rotation matrices ae used torepre ;autDeverotationofthelustationTransion APPendix whichisencodedinthePROMSasset‘Siticcs aenadomovegrepic chareciers aboutonTh thebtdescription mapofAppendix A saecuitsFatston fromamaximumsie-Ti2,,Asmentionedsbove,headercard200intrealy iicorpreset thetangentotheangeoftaway Maia10thesameaceconfigurationasthebse Jeoerica esefrom—45desrees©+45ratedsomewhat differently thawthebasicpipelineSeneyputomaramakercard201willyy2Afenerblockdiagramrepresentingoepesaoe eanmanipscard202"°°calyPreferredaan on ‘aregenerated internally by Withreference toFIG.4,dataintheformofpointmatrix maker files and normal files enters header card 300 through Isparent thathecomponentwhichformmattxFIFOpatiUlimotoftheteardsinpipe makercard20couldbeprogrammed wingty4-35line200,however,etnaalcommands(oheader able technique toaccomplish the functions descrit ccard300areenterthecardfromCPUbus808through shoveAnexampleofonesaabsetofmicrocode CPUnetae 370-Baseduponthedetaeeivedfom fretructonswhichma rogrammalikpioeinebas86andthecommandsreceivedfromCPU, takercard201setforthinAppendix B.Appendix APRgog“wateears'S¢9tengenerateitowncom {lusterabitdescriptionmapwhichreferenceseach4Penartaneactneterithsesuencer lineofthemicrocode ofAppendix B(0Theperi eee OOM 390,Thecommands20 Tecan nthe: miesocode PROMS. U182-U108 ang anes ae ee ows nipehne 200through UISICUISS (ceFIG. 3B)atwhich themicrocode seer Oe dech othe ther pipelineStored.Thusinordertomakeandusematrinmakercarlysuchtcardsprocescontoldatapoints,Altera:card201inaccordancewihthepresentlyprefered4stively,suchcommandsmaybesenback©CPU800 Embodiment ofthe present invention,oneneedonly"CPUbon806 Smtr thematrix maker TC's using thepnconnections "Hendcrseed 300 also includes RAM 360 which may Ss'shown inFIG. 3B,and then encode thePROMS pe'iaed totemporary sore data orcommands. Also UrakUtas and UISI-UISS using themicrocode of eades cand M's provided with anintemal clocking Appendix B,which isencoded inthePROMS assets contol 320 which controls thefunctions ofheader ford nthebudescription map ofAppendix A. Seat 00 Mat Malipe Cad ng Reference isnextmadetoFIGS.SA-SE, whichilutrixmultipliercard202hasthegeneralconfigurs- ateinmore,dealonepreferedembodimentof& tionofthebasicpipeline cardofFIG.3.However, detailed electrical schematic diagram derived fromthematsmlecard202doesnotincludethealow”5blockdiagramofFIG.&Thoseofordinarysilinhe Ingcomponents twister236,shiler282,sine/cosine artwilofcourse,appreiatethatvariousmodificationsinput 258constants PROM 284latch286dataPROMsfotheetallodschematicdiagramsofFIGS.5A-SE 3ccnp Ich30h,adseconoptayesadewhopringomtheetalandshake Ghoracerats ofthe invention, Thus, the folowing "Themajor function ofmatrix multiplier card 202is to«0description ofthe detaled schematic diagrams ofFIGS. cone two34aie afmthecen SacBee came nasly meformation mets, Toaccomplish thi, fraisoneprescalypreferedemboditent. TheVarious RAM244andYRAM238areulizedonthscard.Atcieultstagescoresponding toeachofthefunctional Bip tine XRAM desholds tecurrent tansformation blocksofFIG.#areoulinedinFIGS.SA-SEbybold, imattiandYRAM238isusedtosoretheincoming6Sdashedlinesandarenumberedwithlikenumerals mnattsuppliedbymatrixmakercard201obeconcate: SchematicdagramsSA-SEsrerelated10onean- ted withthe current transformation matrix When the other bymeans ofvarious connection points T=0" lo-Productmatesiscompleted,theproducedmatrixseatedalongthesidesofeach figure. Inconsidering the 4,646,075 23 ua detailed schematic diagrams ofFIGS. 5A-SE, there- with microcode PROMS and latches 230ofthebasic fore, connection points having likenumerals should be pipeline card, theoutput ofthePROMSs ofheader card considered asbeing electrically connected s0astopro- 300arelatched bylatches U290, U277, U202, U266, vide fordata transfer between thecircuit components _U221, U243, U219, U30S, U204, U2S4 and U208. A iMlustrated intheseveral Figures. 5.pullup circuit isalso illustrated inFIG. 5Bwhich hasa Inaddition, asinFIGS. 3A-31, throughout Figures plurality ofnumbered flags. Such flags represent con- SA-SE, integrated circuitsarerepresentedbyanumeral nectionsbetweencorrespondingly numberedflagsin preceded bytheletter “U." Resistors andcapacitors are FIGS. SA-SE. Gesignated bynumerals preceded bytheletiers “R"and __InFIGS. 4andSC,ALU 350ofheader card 300is “C,” respectively. Various testpointsontheschematic10illustrated.ALU350comprisesbitsliceprocessors diagrams aredesignated bynumerals preceded bythe U229, U241, U283, andU264. ALU 350alsocomprises letters “TP.” Also, switchesaredesignatedbynumerals alook-aheadcarrygeneratorU2I7connectedtoall precededbytheletter“S,"andindicatorsaredesig-fourALUslices. natedbynumeralsprecededbytheletters“DS.” FIG.SDillustratesRAMstorage360ofheadercard ‘Thespecific circuit components which areused in1300.Asshown, RAM storage 360comprises RAMs accordance with thispreferred embodiment ofheader U236 andU234. Drivers U259 andU257 arealsopro- card 300 areidentified inTable 2below. Those skilled _vided fordriving data from RAMs U236 and U234. In intheartwill, however, readily appreciate thatawide addition, RAM storage 360also includes multiplexers Variety ofdifferent specific circuit components would U297 andU29S with associated drivers U248 andU246. alsoproduce acceptable results. 20Multiplexers U297 andU295 areused totestand/orReference isnowmadetoFIGS.4andSA.Asreadvariousindividual bitswhichareinputfromRAMsshown,FIFOinput310ofcolorboard300comprises U236andU243orfromtheheadercarddatabusFIFOs U238, U226, U299, and U286. Each chip is16 through drivers U248 and U246. words deep by5bitswide. Aswith FIFO 274ofthe Aserial input circuit (comprising ICU224), isalsobasicpipelinecard,theinputdataholdtimeforFIFOs25showninFIG.SD.Thiscircuitallowsheadercard300'U238, U226, U229, and U286is70nanoseconds. There-tosignalwhenitisreadyfordatainputandalsoto fore,input datalatches U280 andU273 areprovided in receive facevisible bitsfrom shader card 204tobe order tomeet theFIFO hold time andallow fullspeed transmitted back toCPU 800, asdescribed above. system operation. Inaddition, output latches U212 and Referring nowtoFIGS. 4andSE,theCPU interface U261 arealsoprovided toallow output asfastaspossi- 30ofheader card 300isconfigurated similarly tothatof blefrom theFIFOs with adata output access time of75 thebasic pipeline card. Accordingly, CPU interface 370 nanoseconds. Data flow through FIFO input 310is ofheader card 300comprises acontrol port, astatus controlled byacontrol circuit illustrated inFIG. SE. port, aninput data port, anoutput data port, atrans- FIG. 5Aalsodepicts pipeline output port 380. As ceiver, andanaddress decoder. Each ofthese compo- illustrated, output port380comprises latches U223 and35nents willbedescribed briefly U237. Thus, commands anddata output which arefrom The control port portion ofcomputer interface 370 header card 300can belatched inlatches U223 and comprises ICs U308A, U308B, U307B, U280A, and 'U237 while such commands anddata areread byvector U301A. CPU 800writes control information into con- ‘multiplier card 203(seeFIG. 2). trolport278.Such information comprisesaresetbitand FIG.8Aalsoshowssequencersection340ofheader40abitusedtoindicatethatallofthepipelinecardshave ‘card 300.Sequencer section 340comprises sequencers passed thePower-on Confidence Test, described above. U255, U244, andU232. Aswith thebasic pipeline card, LEDs areprovided toInaddition, sequencer section340includesamapping _indicateboththatheadercard300haspassedthePow PROM U220 and alatch U207. Thus, when acommand —_et-On Confidence test(DS1) and that allofthecards inisreceivedfromCPU800,thecommand maybedriven45pipeline200havepassedthePower-onConfidenceTest tolatch U207 andinto mapping PROM U220. (DS2). The status port portion ofCPU interface 370 ‘Anext address control, comprising PROM U267 is comprises driver U283 andassociated flip-flops U294B,alsoprovided insequencer section340.Theoutputof_U307A,andU307B.ThestatusportenablesCPU800toPROM267controlsselectionofthenextsourceof_readseveralbitsofinformation, therebydetermining,addressforthesystem.Thisnextaddressmaybere-$0thestatusofvariousheadercardfunctions,ceived from either microcode PROMS 330ormapping _The input andoutput port portions ofCPU interfacePROMU220.Further,sequencer section340comprises 370comprise latchesU260&U258andU249&U247,condition multiplexers U21S andU228 toinput test respectively. Drivers U271 andU269 areprovided to conditions tosequencers U2SS, U244 andU232. drive datafrom input latches U260 andU288 onto the FIG. $Aalso illustrates theinternal clock and mode $$data bus ofheader card 300. Transceivers U296 and control ofheader board 300.Aswith thebasic pipeline U285 allow CPU 800toreceive data from header card‘card,someoperations performed byheadercard300300throughoutputlatchesU249andU247andtoinput‘maytakelonger thanthetypical header cardcycle time. data andcommands toheader card 300through input Accordingly, counter U201 isprovided toallow for latches U260 andU2S8.selectionoftheappropriate cardcycle time. Inaddition, 60 Theaddress decoder portion ofCPU interface 370 thisportion offthecircuit contains numerous flip-flops comprises ICU311A. This circuit allows header card ‘andgates which allow selection ofvarious operating 300todetermine whether theinformation ontheCPU modes forheader card 300. That is,thecircuit controls busisdestined forheader card 300orforsome other thesource ofcommands and data being input toand portion ofthesystem. output from header card 300. 65 FIG. SEalsoillustratesacontrolcircuitwhichisused Referring now toFIGS. 4and $B, microcode tocontrol theinput FIFOs 310 illustrated inFIG. 5A.PROMsandlatches330comprisePROMsU291,U278, Thiscontrolcircuitcomprises IC’sU293A,U293B,and'U203, U265, U230, U242, U218, U304, and U208. As U289A, together with associated circuitry 4,646,075 25 26 Referring toTable 2below, the various integratedCe seieaeersteed inhewehennie|————TABLE 2eontinyed__ ilostrationsofFIGS.SATSEatesetforth.Thecompo: entComponenoftheenderGu nents areidentified bythesame numbers used inthe um TaeFigures.Resistors are}wattresistorsandresistance isS th EiiscralStated inohms. Unless otherwise indicated, capacitance vm ess isstated inmicrofarads. ee me tie Mere taeon Mere Tan Components ofthe Heder Cd car dss ‘Integrated Circuits. uae -— .tie ditsiaNo Type on roe‘aor 74S16 oan Trbwnstar Mee Gn musies vant isp s tae sat Uae see cnn setUios isn tne Ber ta sere Gn serovane sere van ss vas eros tan pata tito eo x0 tao hewn ua Sarvs tar isetan Saran tm se ua sv bes sstl2tite sets Une yestats sex Uns sat tite Sires vse satsUNT ‘AFIRD a ‘U27 ‘4231an ise ome wisius See te sass te ism vi water tan Hest oar sestan ke toon Mtseefe seine x0 ve neste uae atsits Une se tas ie hi Henstiie si2s vine Mtsoe ta wee om nesteca east van mise tas sors 3s rid Hawtio ie bio Seren Hess ont rao Gn Bt on Nett Gn seteSee une 4801.90 No. Resetis ssw ©sane tiie ‘eoia.90 rr oe tan nee me A ca tis 3 ae ts Meo te 3K tho nr A aKtat mae ® nae akte Has a ia tae iene mr iobase Buia us Bk Uns seo no aUe fru mr avie ow so mu 3k tae frau mi ie ths hes me o Uno hem Aa teusr sits te Eytn eros gS 2 as ire ie Ey U2s4 TAF374 8 RI 470us mia no % Use se u 2 Us Die Re pad va ese Re xtas tira Re pi tio Hen © RS pi tie ese Be pd te tee me ~ tie ise a ” tie BOL Be a oe ss Re paee fens « Reo =te soe Bl 2Uber mene RY = tier He atio piste Camdes 4,646,075 27 28TABLE2contin ‘AppendixD,whichisencodedinthePROMSa8setTABLE teminned__ RRSittaspfapofpendsAatt Componenes ofteHet F.Shader/Hidden Surface Cardes a —___ ‘Shader/hidden surfacecard204hasthegeneral con-cir oF 5figuration ofthebasi pipeline card ofFIG. 3.How- baa No.oFever, shader/hidden surface card 204 does not include she won thefollowing components: twister 296, XRAM 24,ie __tt Sieeosininput258,stack260,PROM266,secondary card300couldbeprogrammed usinganysuitabletech:pfey"PUtOftaecard28rectS08 nig0accomplihefunctionsdesertedabove,An”Sharcard2recivsbthcommandsanddaafrom stichmaybeesedtoprogramhearcard3000°eseneshadercard204tocomputewhetherfaces enerate theappropriate Commands forcontroling the15 PMEOry sackray. Erefontorbeckfacing(facevisibleornot)andalsoto ther cards inpipeline 200issetforth inAppendix O. compute anappropriate shade fraction foreach face.‘Appendix Nitrates «bitdescription mapwhich OMPUIEanappropri shadefractionforehoe ‘ferences each line ofthe microcodeofAppendixOroartvisibledaithensen1Beadercard390whe theparticular location inthemicrocode PROMs U291, 99. scanconverter {U278, U203, U26s, U230, U242, U218, U3O4, andU20S 20“riapparent thatthe components which formshader (ee FIG. 38)atwhichthemicrocodelsstored.Thus,in.,t4/apparent intthecompo formshader Gridertomukeanduseheadercard300inaccordance Couldbeprogrammed winganysuitable tccihihepresently preferred embodiment ofthepresent GUEt@accomplish thefunctions described above,An Itvention oneneedonlyconnect theheader ICsusmng _CTample ofonesuitablesetofmicrocodeinstructions thepinconnections asshowninFIG,$B,andthen25ICHmaybeusedtoprogramshader iswet encodethePROMsU291,U278,U203,U265,U230, forthinAppendix pendixAillustrates abitde-encodethePROMSU1, U2TE,U2iS,U26S, U290,rion mapwhichreferences eachneofthemicro ‘2,U2Usb,andU20SwingthemicrocodeOfCodeofAppendixEtotheparlalocationinthe Appendix whicisencodedithePROM tmlcrovode PROMs Ul42-Ul49 and.UISI-UIS3 (eemhinthebitdescriptionm soFIG.3D)atwhichthemicrocodeissored.Thus,in ‘Vector multiplier card203hasthegeneral configura- ordertomakeanduseshader card204inaccordance oN to lier card209hashegeneralconfigureihthepresentlypreferredembodimentofthepresent vectormultipliercard203doesnotincludethefollow- nihsandneedonlyownitoeeeoaidaero Guster296°RAM2a,shifter252,thepinconnections ashowninsadthenaeeeareapa358constants PROM284,latch286,35en60dethePROMSUI42-U149andUiSt-U189using penta pringTred themicrocode ofAppendix E,which isencoded inthe ‘Vector multiplier card203isthemostcomplex pipe- PROMS assetforthinthebitdescription mapofAp- linecardwithrespect toitsposition inpipeline 200. pendix A. ‘Twopipeline cards canwrite tovector multiplier card G.Clipper Cards203,anditcanwritetotwoothercardsbelowitinthe40_Eachoftheclippercards205-209 hasthegeneralPipeline. Accordingly, vectormultiplier hasfoursys-Configuration ofthebasicpipelinecardofFIG.3.How-temsofdatatransferhandshakes: secondary inputhand- _€V¢r,clippercards208-209donotincludethefollow-shake 270,primary inputhandshake 272,@secondary ingcomponents: twister 236,XRAM 244,sine/cosine‘output handshake (secondary output isbyCPUbus input258,dataPROM 266,secondary inputlatch268,808),andprimary output handshake 290. 45andsecondary inputhandshake 270. The purpose ofvector multipliercard203istotrans-_All5clippercardsareconfigurated as3Dclippers, form points coming intoitfrom headercard300bytheandeachclippercardclipsagainstoneplaneofthe ‘currenttransformation matrixsupplied bythematrix viewingfrustum(seeFIG.1B).TheDclipper(clippermultiplier card202.Vector multiplier card203then card205)clipsatz=D, the“nearclipping plane.” Thesends thetransformed points outtotheircorrect desti- $0+Aclippers (clipper cards 206-207) clipattheleftandnations: datapoints toclipper cards208-209; andtrans- rightviewing boundaries, andthe=Bclippers (clipper formed normal vectorstoshadercard204 Cards208-209)clipatthetopandbottomviewing TT'sapparent thatthe components which form vector boundariesmulti card23could teprogrammed ung any Thepoints coming intoclipper cards 208-209 areof suitable technique toaccomplish thefunctions de-55theform (xg,ys2e), (ic.points inthree-dimensional qiibed above Anexample ofonsultble setofmicro. space). When aclipper cardclip, itcomputes theinter- weaeiistoctions whichnay beuedtoprogram vector section point ofaline orcurve withthe appropriate Geaipucr cand303 nseforthinAppenaix'D”Appen- clipping plane. Reference isnowmade toFIGS. €7N durwicstrtes abtdescupton stpwithreferchees which ilutrate theoperation ofclipper cards 208-208 tach lineofthe microcode ofAppendix Dtothe partic: «0inmore deta Gistochson tsthemicrocode PROMs U2-U109 and FIG. 61s state diagram which illustrates how elip- UISICUISD (ceFIG. 3B)atwhich themicrocode is percards 205-209 move from slate osate inprocessingoredThusinordertomaeandusevectormliplier Stapointsrepresenting straightlinesandcurvesSats ‘bostnacsordance with thepresently prefered. Thesystem sist inialized toSateS.WhileiState Embodiment ofthepresent invention, oneneed only 65S,ifpoint comes inwithacodeofCloseorNext,this Sonnect thevector'muluplier TCsung thepinconnec." ivan erro. Thus, 0action istaken andthesystem loneasshowsinFIG.3B,andtheneneodethePROM.remainsinStateIfapointcomesinwithaFistcode, Uns?UIs)andUISI-UIS9 usingthemicrocodeofthepointsprocessedandthesystemmoves10SateA. 4,646,075 29 30FromStateA,aClosepointwillreturnthesystem BezierSplitsubroutine instep550c(seeFIG.71).AfterbacktoStateS.If,whileinStateA,eitheraFirstorastep5504,thesystemgoestostep524wherethesystemNext code isreceived, thesystem remains inStateA.If,stateflagissettoStateA.Thesystemthenreturnsto while inState A,aBezier code isreceived, thesystem theGetCommand subroutine 502.movestoStateB, 5._Theflowchartillustrated inFIG.7CistheProcessFrom State B,aClose orFirst code isanerror and Bezier subroutine 525. First, theroutinegoestostep526 thesystem returns toState S.However, while inState andteststhesystem stateflagtoseeifitisinState A. BaNext code willmove thesystem toState C. Iftheanswer isno,control goes instep 527toset InState C,either aFirst orBezier code isanerror system state flagtoState S,andthesystem returns to ‘andmoves thesystem toState S,From State C,aClose 10theGetCommand subroutine 502.‘codeisproperbutwillalsomovethesystemtoStateS._Ifthesystemstateflaginstep526isatStateAajump.If,while inState C,aNext code isreceived, thesystem ismade tostep528.Vector R,isthen putintoanewmovestoStateA. storagelocationBo.(VectorR,isthestartvector.)The‘Themain clipper flow chart isillustrated inFIG. 7. Vector RisnextputintotheBystorage location (RisReferring tothetopofthe flow chart, either ahardware 15thecurrent vector being dealt with). The system state reset oraCPU reset willcause thesystem togointothe flagisthen settoState B,andthesystem returns tothe Power-On Confidence Test subroutine 500. Asex- Get Command subroutine 502. plained above, thissubroutine performsatestoncertain_TheProcessClosesubroutineisillustratedinFIG. Systemfunctions. EitheraPipelineInitoreitherofthe7D.First,instep831,aconditional jumponthesystemabove-mentioned resets will cause aninitialization of20state flag isperformed. registers instep501.Thesystem thengoesintotheGet _IfthestateflagisState SorB,thesystem immedi-‘Command subroutine $02.Dependent onthecommand _atelyjumpstostep35.Thismeanstherewasanerror,obtained through theroutine, control willpassinstep _since thesystem should nothavereceived aClose Code 503toeither thechange input/output (XIXO) subrou- atthispoint. ThestateflagisthensettoState Sinstep tine504,theProcess New Viewing Window subroutine 25535andthesystem returns totheGetCommand sub- 505, theSet/clear Edge Mode Subroutine $06, aPoint routine 502. subroutine, oritwill pass thecommand through to _Instep531,ifthe state flagisA,thesystemthengoes othercardsinstep510(ifthecommandisnotforthistotheClipSegsubroutineinstep5450(seeFIG.7F). card),After step 5486, thesystem goes totheThis Point sub-InthePointsubroutine, thesystemwillfirstgeta30routineinstep540c(seeFIG.7E).Then,instep$45c,point called “Vector R"instep507.Then instep508 thesystem again executes theClipSegsubroutine (see thesystem extracts from thepoint thepoint code, and FIG. 7F). various control bits.Ajump isthen made instep509 _Instep$33,thesystem tests theAny Output flagto depending onthecode associated withthatpoint (the seeifitisset.Ifthe flagisnotset,thesystem jumps to code being either “First,” “Next,” “Bezier” or35step535,setsthestate flagtoSandreturns theGetClose”), ‘Commandsubroutine $02.IftheAnyOutputflagisset,“Thesubroutine illustrated inFIG. 7AistheProcess ajump ismade from step $33tostep 534where the First point subroutine 515.Step516issimply ajump, point code forpoint Ryissetto“Close.” TheSystemdependent ontheStateofthe system (seeFIG. 6), then jumps totheOutPoint subroutine instep 570a. IfthestateflagisBorC,thesystem jumps tostep40Then, thesystem executes step535asdescribed above 517,wherein thestate flagissettoState 5.Thesystem andreturns totheGetCommand subroutine. then returns totheGetCommand subroutine 502. Back instep 531, ifthestate flag isC,thesystem IftheState instep516isState SorState A,thesys- jumps tostep$32andputstheRVector intostorage temjumps tostep518toclear(orsettofalse) thatAny location B3.Ajump isthenmade totheBezier Split ‘Output Flag. Thevector R(composed ofcomponents 45subroutine $50) (seeFIG. 71).Onreturn from that Rx,RyandR,)isthenloaded intoastorage location subroutine, thesystem jumps tostep548andoperates called Ry(R-First) andajump isthenperformed tostep from thatpoint onasdescribed above. 540which istheThis Point subroutine (seeFIG. 7E). __TheThis Point subroutine $40isillustrated inFIG. ‘After astep$40, thesystem state flagissettoaState TE.This subroutine goes firsttostepSia andtests to ‘Ainstep 519andthesystem returns totheGet-Com- $0seeiftheVectorRisvisible(seeFIG.7H). mandsubroutine 502. Iftheanswerisno,thesystemjumpstostep$41,puts ‘TheProcess Next point subroutine 520isillustrated theVector RintotheR,storage location, andthen inFIG. 7B.First instep 521,ajump ismade dependent returns tothecalling routine. ‘upon thesystem State flag.Ifthesystem isinState S, Iftheanswer tothevisibility testisyes,thesystem thesystem simply returns totheGetCommand subrou- $5_goes tostep578aandjumps totheOutBuf subroutinetine502.IfthesystemisinStateA,thesystemjumpsto(seeFIG.7M).Afterexecutingstep5752,thesystem theClipSegsubroutine instep$45a(seeFIG. 7F),then thengoestostep541,asdescribed above.totheThisPointsubroutine instep$405(SeeFIG.7E)._TheClipSegsubroutine 548isillustratedinFIG.7F. ‘Thesystem thenreturns totheGetCommand subrou- This subroutine enters with twovectors RoandRi. tine502 6First, theroutine goes into step 511b todetermine Instep$21,ifthe system stateflagisintheBcondi- whether Rois visible (seeFIG. 7H).tion,ajumpismadetostep$22whereinVectorRis_IfRoisnotvisible,thecontrolgoestostepS11ctotest. loadedintoastoragelocationcalledBz.Thenthesys-iftheVectorRyisvisible.IfRyisnotvisible,thesystem temstateflagisthensettoState Candcontrol returns returns tothecalling subroutine. IfRyisvisible, control totheGetCommand subroutine 502. 65then goes instep $85a, totheIntersect subroutine (seeInstep521,ifthesystemstateflageisC,ajumpisFIG.7G).Afterstep585a,thesystemgoestostep$46.madetostep523wheretheVectorRisloadedintoaThere,thepointcodefromRiiscopiedtotheintersectstorage location Bs.Theroutine thenjumps tothe point (1)code. Also, theflapandfacevisible bitsof 4,646,075 31 32 point Iarecopied from Ro.Thesystem thenjumps to Theevaluation made forthe+Aclipper (clippertheOut-Buffsubroutine instep575(seeFIG.7M)andcard206)is:then returns tothe calling subroutine.ThstepS11,atthetopofFIG.7F,ifitisdetermined RecRMA/DY”thai Vector Rois visible, then thesystem control goes to.$ SepS1idtotestwhether Vector Ryisvisible Irboth Theevaluation made forthe—Aclipper (clipper arevisible, thesystem returns tothecalling routine. If ard207)is: Vector Rrisnotvisible, thesystem jumps instep $856 thentotheIntersect subroutine (seeFIG.7G).After0 “Ra>—ReMA/D)~S585, the system moves tostep 5466, copies the pointSoacand PaesVisible bitforVector RytoVectorland,THeevaluation madeforthe+Bclipper(clippercard setstheFlapbitofVector Ito“OFF.” Thesystem then 208)is: jjumps to theOutBuf subroutine instep 57Se andthen nervy” Intersectsubroutine 58SisillustratedinF Teer aieSoaveeRoadRe “Theevaluation madeforthe—Bclipper(clippercardFirst,ajumpismadetostep$86andavalueforFis208)is: computed, asdiscussed below. After computing F,the onyRAED) intersect point iscomputed instep 887. The Xcompo: nmonhThe¥comeee1a,equalsROr+PReTheBezSplitSubroutine 550sillustratedinFIG.71.iROvr"RH,ROpKThe2component ofkeSts wncetegrates(etSad0 intersectvertor:IpisROO[F*(R1—RO:)]. Thesy5-routine$90(seeFIG.75)isused,therearethreepossi- temthenreturnothecalngroutine. apBleatsreturnsVisible,InvisbleorSplit_ThevalueforFscomputeddependentuponthe“>"AthtpoftheBezSplitsubroutine,takeVectorBSorcularclippes beingusedAlphaisA/D,BettandputiimthestoragelocatonferVectorRuinsteptainedfromaprevious command inputtothecardS51ennstepS82thesideNagissettovisibleandthe stack isclear called the New Window command. For the DClipper(dippercandBn8,FebZo)/21~ Zotisthecone“, TETouinethen jumpstostpS90evans thGPRSinntheZeomponesafthe Revector divided "atsofthe fourworkingpoints:VectorsBoBr,BrandbytheZcomponent ofVectorRiminustheZcompo: PhesatusisSplit,thesystem bytheZcomponent ofV1 nustheZ_con statusisSpit,thesystemjumpsostepS134and emtoftheRovectorForthe+ACpper(GHPPereArd goesoteSplitsubroutineeeFIG.TL)TeSlit 35itsubroutine will return two new sets ofcurved points: .VectorsLeft0,Left1,Left2andLeft3(Lo,Li,Lz,and7oe ee La)and Ro,Ri,Ra,andRy.Thesetwovectors representfo~Aiphe sand theleftandrighthalvesofthecurve.Instep553,thesetofvectors forthe right halfofthecurve(Ro,Ri,Rz,and Forthe—AClipper (clipper card207): 4Ry)arepushed intothestack. Then, instep554,set Bo=Lo, B}=L), B2=L2, andBy=Ly. This uses theleft fe xo+Alpha*20) halfofthecurvethatwassplitandmakesitthenew WesAla Zar OTs AZT curve ofevaluation, From step 554, the system will return back tostep $902 again. Forthe+BClipper (clipper card208): 45 Tatstep590a, iftheGetStatsubroutine returns the answer “invisible,” thesystemgoestostep$61tosetthere (v=peut29 SideFlagtoinvisibleandthenproceedstostep562Tey eT ‘which isexplained more fully below.jo._Fromstep$902,itheanswertotheGetStatussub- Forthe—BClipper (clipper card209): routine is“visible.” thesystem jumps tostep555t0see ifEdge Mode ison.IfEdge Mode ison,thesystem e+peasay jumpstostep558tosetthecodeoftheBopointtoa PyiaZ-lsBea “First”codeandturntheflapbitoftheBOpointtooff.ssThen, thesystem jumps totheOutBufsubroutine in FIG. 7Hillustrates theVisible subroutine 511which "step878(seeFIG. 7M). Onreturn, having completed isusedtodetermine whether aparticular point isvii- steps588and575g,thesystem jumps tostep859,whichbe.Thevisiblesubroutine willreturn“true”ifthepointismorefullydescribedbelow.If,instep585,itisdeter-ison thevisible sideoftheparticular clipping plane mined thatEdge Mode isoff,thesystem thengoes to being tested. Thevisible subroutine willreturn fase if60step556 thepoint isontheinvisible sideoftheclipping plane. Instep$86,thesystem determines whether theside ‘After theflagissettotrueorfalse thesystem returns to flagissetto“Visible.” thecalling subroutine Iftheanswer isyes,thesystem jumps tostep559, “Thewaythevisibility isevaluated depends upon the which isdescribed more fullybelow. Ifinstep556,theparticularclipperinquestion. (65.answerisno,thesystemgoestostep$57tosetthecode‘TheDclipper (clipper ead205)Visible subroutine fortheBopoint to“Next” andsettheflapbitoftheBy testis: “Re>D." Ifthe answeristrue,thepointisvisi-pointto“off.”ThesystemthenjumpstotheOutBuf ble;iffalse, thepoint isinvisible. Subroutine instep878e (seeFIG. 7M), 4,646,075 33 cad ‘Thesystem thenexecutes step559,Instep589,the Vector Bo+B1, divided by2.Vector L2isfound by code oftheBypoint issetto“Bezier,” theflapbitof taking vector L)+vector M,anddividingbytwo.Vec- point Byissetto“off,” thecode oftheBypoint issetto torR3equals Vector Bs.Vector RzisB2+Bs, divided Next,” theflapbitoftheB>point issetto“off,” the bytwo. Vector Riisvector M-+Ra, divided bytwo. codeoftheBypoint issetto“Next,” andtheflapbitof$‘Thevector Roisfound bytaking thequantity vector theBspoint issetto“off.” L2+Ri anddividing bytwo.Vector L3equals vector “The system then goes totheOut Bufsubroutine in Ro. step575/foreachofthepoints By,Bz,andBs.After After performing alloftheabove calculations, the ‘executing thesubroutine three times, thesystem goesto system thenreturns tothecalling subroutine. step$60tosetthesideflagtovisible. 10TheOutBufsubroutine 575,isshown inFIG. 7M. ‘Next, thesystem goes tostep S62anddetermines Firs,instep576itisdeterminedwhetherEdgeModeis whether thestack isempty. Ifthe stack isnotempty, the on.Iftheanswer isyes,thesystem goestostepS81and system popswhatever isontopofthestack offinstep determines whether theAnyOutput flagisset.Ifthe 563.Thesystem thengoesback tostep5092 andpro- flagisset,thesystem jumps tostepS83,discussed be-ceedsassetforthabove. 15low.IftheAnyOutputflaisnotset,thesystemjumps 'Atstep562,ifitisfound thatthestack isempty, the tostep$82.There, theAnyOutput flagisset,andthesystemjumpstostep564todetermine whetherthesidecodeofpointRoissetto“First.”flagissetto“Invisible” and,atthesametimewhether _Instep583,setthefacevisible andtheflapbitsofthetheBypointisvisible.Iftheanswertothetestisno,theRoVectoraresettooff.Thesystemthenjumpstothe‘system jumps tostep566andsetstheflapbitofthe20OutPoint subroutineinstep870¢(seeFIG.7N).After point stored asRaequal totheB3fapbit.Then, the step570c, thesystem returnstowheretheOutbuffsub- System returns tothecalling routine routine wascalled from,IftheanswertothetestinstepS64isyes,thesystem_Backstep576,itheEdgeModeisnoton,thesystemJjumps tostepS68andsetstheBscode to“Next,” and jumps tostep577.Instep$77,theAnyOutput flagis theBsflapbitto“off.” Then, thesystem jumps tothe25again checked toseeifitisonoroff.Ifitisoff,the OutBufsubroutine instep875d. After siep578d, the system jumps tostep578andsetstheAnyOutput flagsystemexecutesstep566,aspreviously described. totrueandthecodeofpoint Rato “FIRST.” Ajump is ‘The Get Stat subroutine asillustrated inFIG. 7J.In then made tostep $80. step591,thesystem determines whether Boand Byand Instep577,itheAnyOutput flagison,thesystemB;andB3areallvisible (seeFIG. 7H).Iftheunswer is30goestostep570tojump totheOutPoint subroutine yes,thesystem proceeds tostep 592andtheanswer with theVectorRaasthepointofevaluation. Feturnedtothecallingroutineis“visible.”Thesystem_ReturningfromtheOutPointsubroutine,gotostep thenreturns tothecalling routine. Ifthe answer tostep $79andputthecodeoftheVectorRointotheRzcode 591isno,thesystem proceeds tostep593. storage location. From step 579, thesystem jumps toInstep893,thesystemdetermines whetherBo,Bi,35step580.B,andByareallinvisible(seeFIG.7K).Iftheanswer_InStep580,theflapbitoftheRopointbecomestheisyes,“invisible” status isreturned tothecalling routine flapbitfortheRapoint. Face Visible bitofRobecomes instep594;andthesystem thenreturns tothecalling thefacevisiblebitforRp.Then,vectorRoisplacedinto routinetheRestorage location, thatis,thismeans allthree Iftheanswer isno,status “split” isreturned tothe40vector components RorRoyandRorarestored inthecallingroutineinstep595,andthesystemreturnsbackrespective RalocationsRaz,RayandRaz.Next,thetotheroutinefromwhichitwascalled. systemreturnstowhéretheOutBufsubroutine wasThe Binv subroutine $12 isillustrated inFIG. 7K. called from. This subroutine determines whether avector isinvisi The Out Point subroutineisillustratedinFIG.7N.In ble. The evaluation ofwhetheravectorRoisinvisibleis48step571,theflapbit,facevisiblebit,andcodeprevi- ‘Booleanfunctionwhichdetermines ifthecontrol ouslystoredfortheRovectorarecombinedasparame-point ofaBezier curve isinvisible. Theinvisibility de- terstoform aPoint Command (called Command C). termination isslightly different fromthevisibility func- Then, instep572,aCommand Cisoutput thenRes,Ren tion(seeFIG. 7H)inorder tomake thecurves con- Rey(thecomponents ofvector Ro)areoutput. Theverge. 50subroutine thenreturnstowhereveritwascalledfrom.‘Theinvisibility determination isdifferent foreach of Itisapparent thatthecomponents which form clip-theclippercards208-209.ForfortheDclipper(clipper percards205-209couldbeprogrammed usinganycard205), itmustbedetermined thattheZcomponent suitable technique toaccomplish thefunctions de-oftheRvector(R.)islessthanD-+Epsilon, where scribedabove.Anexampleofonesuitablesetofmicro-Epsilonisasmallnumber(suchas,forexample,4).For$5codeinstructions whichmaybeusedtoprogramthethe+AClipper,Rxmustbegreaterthan’R.*Al- clippercards205-209issetforthinseveralAppendices.pha—Epsilon, where Alpha=(A/D). Forthe—AClip- Themicrocode forclipper card205issetforth inAp-per,Rxmustbelessthan—R,*Alpha-+Epsilon. ForthependixF.Themicrocode forclippercard206isset*BClipper, Rymust begreater thanR,*Beta—Epsilon, forth inAppendix G.Themicrocode forclipper cardwhereBeta=(B/D). Forthe—BClipper,Rymustbe60207issetforthinAppendix H.Themicrocode forclip-lessthan—R,*Beta+Epsilon. percard208issetforthinAppendix I.Themicrocode“TheSplititsubroutine 513isdepictedinFIG.7L.forclippercard209isstforthinAppendixJ.Appendix This subroutine requires theVectorsBo,Bi,Bz,andBs;Aillustratesabitdescriptionmapwhichreferences twoothersetsofvectors(Lo,Li,L2,andL3andRo,Ri,_eachlineofthemicrocodeofAppendices FJtothe Ra,andRa),arederived. 65particular location inthemicrocode PROMs Ul¢- First, instepS14,anewvector Misdetermined. 2-U149 andUIS1-U183 (seeFIG. 3B)atwhich the Vector Mequals vector B;+Bz, divided bytwo.Sec- microcode isstored. Thus, inorder tomake andusethe ond, vector Boiscopied tovector Lo.Vector Liis clipper cards 205-209inaccordance withthepresently a 4,646,075 46 preferred embodiment ofthepresent invention, one tworesets wllause anintalization oftheregisters and Teed onlyconnect theepper ieswing thepinconnec- thecard Teasacshowsin FIG. Band thenensode thePROMS From there ajump ismade intotheGetCommand Uren U9 andUISI-UIS9 using theappropriate mie subroutine 602. After thecommand isobtained i8 cede arAppendices FJ,which iencoded inthe5tested andajump ismade totheparticular subroutinePROMSassetforthinthebitdescription mapofAp-603calledforbythecommand. Thejumpcangoeitherpan fotheX10,VectorHitOn,VectorHitOf,orthePointAviewport Card sebroutine Ifthecommand wsother thantheabove, the Viewport card210hasthegeneral configuration of routine willjump toapassthrough subroutine 607tothebasicpipelinecardofFIG.3.However, viewport10passthecommand tothenextcardahd310Bowsnotinclode thefollowing components. the command isforapoint subroutine 603,«test aie 936° RAM 244sine/conneinpot 250,stack Willbemade irstoseeifthe Vector HitTestton. If twister236,XRAM244,sine/cosineinput256aeitisnot,theroutinewilljumptoProcessPoint620.If secondary inphandshake 270 theVector HitTent ontheHitMipflop isetinstepSea reeves datarepresening 3D1%tadcontro patedotheGetCommand sabrostnepoints cipped tothe inside oftheviewing frustum. The 2, ilncppe 1theinsideoftheviewing rtne TheVector HitTestOnsubroutine 610iiostrated{specific viewport onthesereen. inFIG.8A.Thissubroutine firstturnstheVector Hit specific viewport OntheKEEichfxmview:Tetodinep611clearstheiipopinstep612 en,Sparetharthecomponents whichfomVe"29hensetsheStatsPortDoneittoandtheStats ortcard210couldbeprogiammedwinganysuitable“PorHibittoOinstep618.Aretun'sthen maeothe; falling rontne ‘Anenample ofonesuitable setofmicrocode instruc: 8Anexampleof ttofmr ‘TheVectorHitTestoffsubroutine615isshownin tions which maybeusedtoprogram viewport card210 FIG.8B.Then, thehitflip-flop issetinstep617,andtheinet forth inAppendin K.Appendit Ailusrates abitScttipion maywhichreereces exchlineofthemir25StatusPortDonebitturnedoninsep618crocode ofAppendix Ktotheparticular location inthe “esPointsubroutine 620isillustrated in crocode of Appendix Ktbeparticularlocatontbe6,g¢.Step62,theFlapBi,FaceViseBitandFIG.3B)atwhichthemicrocode isstored.Thus,inCodeareextracted fromthecommand andstoredby ; ; theProcess Point subroutine. Instp 622, theVector R order tomakeanduseviewport card210inaccordance 9jgbrought inwiththePointCommand isthenexamined withthepresently preferred embodiment ofthereset instep28Acondos jumpaso thecodeofhe Itventiononeneedonlyconnecttheviewport 1¢'sstep623.4conditionsthing thepinconnectionfsshowninFIG.3Brandthen nndisthenmade.astep624ontheets catethePROMsUI42-U149andUISI-UIS9usingtheCode8BezierameeoeinResot cred iiPROMSUIG-USandUISL-UIEDangorewcarApipreviowlysoredRiput yemicrocode ixK,whichisencodedinthe35intoBo.ThecurrentVectorRisthenputintoBy.ThenPROMSassetforthinthebitdescription mapofAP-~instep628,anothercommandwithvectorisretrievedpendinA andplacedintotheBastoragelocation instep626,In poder Card epQ27; third command endtheassociated vector f Exploder card 211hasthegeneral configuration of then retrieved. From that command, theFace Visible theHseptne cardofFIG.3,However, exloder athePapbitandtheCadeareexacted tp628)card211doesnotinclude theflowing components: “andstoredinLocation ByandR(step628ASumpiwiser236,mulipcr268,XRAM244,sir282thenmade10theExplodesubroutinestep638).After dataPROM266,secondaryinputlatch268,andsecond-630.*ia.ump‘ep sryinphandshate 20 , 45Atstep63,theRpoint(Rvector)istransferred toThicardperforms twounrcated functions ex.heRta lation, Thelap toreinthe§Plodesgurvesintosegments,andperformstheVector—_Flapbit(FBs)storagelocationandtheFaceVisiblebitit Test inthe SFace Visible bit (FVBs) storage location. A Exploder card21takesthepinsintheatasteamjumpisthenmadetostepG1InstepDtthecodes itrecognizes ascurves andexplodes these points into 50tested toseeiticlose code. Ifthe answer iNo,seaightinesegmentswhichaeshortengsthe"etmtotheclingbowtie.IfheanswerYes, Scgmens appear smoothly curved onthesefeen afer jump tosep 6482.Scanconversion. Points’ which arerecognized as” Step64Sbistheoutputofanedge.Anedgerunsfrom straight edges thedatasteam arepassed through by Rto Ror from thecurrent point (tothe First Pottxplodercard211Dasrecognitionithepontsteam#5(kp),withtheRyFapandFaceVisebisAfteridenbymean ofthescade"wichwataches 0upsting thee, weretrotheclingsoto tach point inthe datastream, tineBungeonFetewingwindowBackp10sep2ifhepointhsaNex radevetysmallandpositionedoveraselectedposition edeasceiated with,Jumpimadetostep Ifapoint comes through viewport card 211toeaploder 60648, theoutpet subroutine. Anedgeisoutputthatgoes Card 212,a“hii epistered: Onthether hand ifthe "from theReepoint tothecurrent point orthecurrent Slippers have clipped everything away, nopoinis Will vector Rywiththe FlapbitandtheFace Visible ithatfeachexplodercurd211andnotiogistered reasocatedwiththeRspointAjumpsthenmadeto Ticitrveiwcath inownsherbow epandthetbocosinesadcr tinesthatwillbedesribedindet shovethers hardwave rest oraCPU reset causes jump Back tostep 629agtin, ifthe point were “Firs.” a tothePOC subroutine 600. The next step down 601 jump ismade tostep632andthecurrent vector Ris Shows thatPipeline Int(PLLINIT) aswell wtheother placed intheRy(orFirstPoint storage locations. The 4,646,075 37 38routinethenjumpstostep630andcontinuesasde-seefitisatenoughtooutputandmakethecurvelook scribed above. smooth.‘TheExplodesubroutine isillustrated inFIG.8D.__IftheanswertotheBooleanexpressioninstep641is “Thesubroutine isentered with Bo,By,Bz,andBsvee- No,ajumps made tostep638andthesystem continues tors,together withaFlapbit,andFaceVisible bi. 5down tosteps639,640and641Firstajumpismade(0step636,whereVectorsBo,_Iftheanswertothequestioninstep641isYes,ajump By,ByandBsaremultiplied byascale factor, suchas, ismade tostep64SC. ThisstepisajumptotheOutput forexample, 2Ajump Isthenmade tostep637,where subroutine tooutput anedgefromvector Botovector VectorCoiscalculated.ThismeansthatboththeXandBs,butthevaluesinBoandBsmustbefrstdividedby the¥components oftheVector Cowillbecalculated. "©thescalefactor. Tocaleulate Co ‘After theedgeisoutput, ajump ismade tostep642andatestmadetoseeifthesiackisempty.Ifthestack3p 2m+8) jsempty, jumptothecalling subroutine. IfthestackisoS ‘notemptyinstep642,jumptostep643topopthevec-15torsBo,Co,Bs,andC3offthestack,thenjumpbacktoNext,Ciscalculated: step640andstarttheprocessagainasdescribedabove.“The Output Edge Subroutine 645 isillustrated insew-atm+ oo FIG.BE.Instep646,anedgecommandisoutputwith cya theappropriate FlapandFaceVisiblebits.ThentheX 20Value ofthe first endpoint isoutput, together with therectorCisnow Yvalueofthefirstendpoint.TheXvalueofthesecond TheVectorCarisnowcalculated endpointandtheYvalueofthesecondendpointarethen output. Areturn tothecalling routine isthen cn=OED made.? 25Tvsapparent thatthecomponents which formex- plodercard211couldbeprogrammed usinganysuit- ‘TheVector Bysis nowcalculated: Abletechnique t0accomplish thefunctions describedabove.Anexampleofonesuitablesetofmicrocode1BD ey 4oinstructions which maybeusedtoprogram exploderom) card 211211issetforth inAppendix L.Appendix A illustrates bitdescription map which references each AAjump isnow made tostep638.Thevector Cis lineofthemicrocode ofAppendix L.totheparticular divided byfour (Cy) andplaced back into Cy. The gcation inthemicrocode PROMs U142-U149. and value currently invector Cyisalsodivided byfour(},,Ui81-U183 (seeFIG. 3B)atwhich themicrocode isC3)andplacedbackintheC3storagelocation.The**stored.Thus,onordertomakeanduseexplodercardvectors By, Cx, Bs,and Cyarethen pushed onto the 211inaccordance with thepresently preferred embodi- stack and ajump ismade tostep 639. Instep 639 the ment ofthepresent invention, one need only connect vector Cois divided byfour (}Ca)andplaced back into theexploder IC's using thepinconnections asshown in thestorage location forCo.Thevector Bais placed into4gFIG. 3B,andthen encodethePROMsU142-U149and thestoragelocationforBs,ThevectorCiyisplacedinto“U1$1-U183 usingthemicrocodeofAppendixL,which thestorage location forCs.Ajump isthen madetostep_isencodedinthePROMSassetforthinthebitdeserip- 640.tion map ofAppendix A. Instep640,anewvalue forVector Cyis calculated. J.Incremental Form CardThatcalculation is: 44s_Incremental formcard212hasthegeneralconfigurationofthebasic pipeline card ofFIG. 3.However, the io incremental formcard212doesnotinclude thefollow-Se ingcomponents: XRAM244,sinc/cosine input258, stack 260, secondary input latch 268, and secondary “ThenewVector Byyis alsocalculated 40input handshake 270."The basic input tothe Incremental Form card ispairsweap ‘ofpoints.Eachpairofpointsdefinesanedge.Thecard Incw Converts thisdescription ofanedgeto“incrementalform,” which isanalternate description ofthesame jumpismadenowtostep641fortwotest55edgemoreappropriateforscanconversion.Thebasic archjumpismadenowtostep644fortwotess.They*Courofthecardisedgesstoredinincremental form“Thecardhastwoothermajorfunctions.Ifthecardis1scurs(Epson) putinto“vectormode”(byanappropriate command),itconvertseachincomingpairofpointsintoathin and:@rectangle roughly two pitels wide. This rectangle is output asfour edges inincremental form. This thin1sCursepsion, rectangleisthe“vector.” “The other major function ofthe card is“lapping.” If ‘here Epsilon is,forexample, zero. anincoming edgehasacertain flapping bitset,theedge 65istranslated slightly (about one pixel) inadirection “TheVector Curis actually thecurvature ofthemid- perpendicular toitself andtoward theoutside ofthe dleofalinesegment andhastwocomponents, Cwrand graphic figure. Thislitleextension isthe“flap,” addedCiry.Thecurvatureofalinesegmentibeingtestedtoineffect,toanedge.Thepurposeoftheflapistogive 4,646,075 39 40 theadjoining graphic figure agood “background” for _(Y1—4 ofthevector width desired foroutput, X1, mt-aliss action inscan converter 820(seeFIG. 1). then thefullwidth ofthevector foroutput forCNT, ‘Reference isnext made 10FIGS. 9-9D which illus- andazero, andazero forthetwoslope numbers.) crate theoperation ofincremental form card212in |Thesecond edgetobe output wilbe more detail “Thechart illustrated inFIG. 9shows thaeither a ageCVE—A HOW,2H, bardwareree nan00APineeee Afterstep719,ajumpismadetostep724whereatestIND ire ismadetoseeiftheEndofVectorflagisset.Ifthe oFoneoftheaboveresetswillthencausethe aseiftheEndofVectorNagia cardto_g0intotheitalization routine701.TheGet10a"sWerisYes,andEndofVector(EOVEC)commans isoutput726andareturnismadetotheGetCommand ‘Commandsubroutine 702isthenentered, and@jump subroutine 702.IftheanswerisNo,anEndofFace madetoasubroutine dependent onthecommandre-Commandisoutput728andtheEndofVectorFlagisceived. Thepossibilities are: set(step 725)andajump ismade totheGetCommand thechange input/output command which willuse 5Soyin 993 ajump totheXIXO subroutine 704, Instep 718, iftheanswer to“Count equal to0?”theVectorModecommandwhichcaneithersetor(Cat07)isNo,jumptostep720andtesttoseeifY1isclear theVector Mode Flag(step 708), greater thanY2.Ifthe answer isYes,goto step721and theFlap Mode command which caneither setor interchange X1andX2,then Y1with Y2andrecom- clear theFlap Mode Flag (step 706) 20pute thecount with thenew Y2minus thenew YI theSetScan Mode command which will cause a” Jumptostep722tocontinueprocessing.Iftheanswer “ump totheSetSean subroutine 750tosetthescan instep 720tsNo, jump ismade immediately tostep tothe 2X or4X mode, or m2.anEdgecommand. Instep722,atestismadetoseeifX1isequaltoX2 Ifthecommandisnotoneoftheabove,iisassumedto25IftheanswerisYes,jumptostep723andoutput(wobeacommandforanotherboardandthePassThrough edges.Thefirstedgeissubroutine 740iscalled topass thecommand throughthecard age,X821HW,ONT.0.0) ‘Wen anyofthe subroutines arecompleted, thepro- gramreturas backtothe GetCommand subrostine 702.30Thesecond Edge is ‘When anedge command isinput tothecard, X1,Y2,1X2,¥2areinput(otep707).Thevalvesarethetwoend EaXIUHW,ONT.)points ofanedgeoralinesegment.XI,Y1isoneend complete the pointX22istheotherend’aferinputingtheedge,.-Aumpisthenmadetostep724tocompletethepro- theroutinegoestoaBranchonModepoint708.The*>““Trtheanswertothequestionstep722sNo,ajumpis modeischecked tose ifitisVector Mode, Flapmode yg. aoonpe ne (DAMS, DXLS)GrneitherIftheVectormode(VM)flagison,jumpeveJoN6012.{S'made toasubroutine thatprocesses theedge forVec- i tormode (step715).Ifthe Flapmode (FM) flagis00,4p nontheedgeisprocessed byaroutine called theProcess pr-2 Edge inFlap Mode (step 709). Ifnotin ether mode, the regular mode must beineffec, s0theedge isprocessed «slope isadjusted totwowords, a formatconven- voces Elgin VeviorMoteabotin 71x2 feetomen fheSeanLieProceso ilustratedinFIG.9A.Theoutputedgesofthissubrou- nisoperation,jum antes tineaeoftheformat:(Y.X.CaisDXMS,DXLS), (9 on ee onesWuhereCatisthecountnumberandDXMS,DXLSare‘©asthePEneatlyNet andsetDeltathemost significant andlest significant slope numbers. syxg" Belts Ye vector width, andcount=2 *Deltainstep716,oftheProcessEdgeinVectorMode"¥ThecountisthecountoftheEndCap(ent)andsubroutine, isatest toseeiftheFlap bitissetIfthe dxms-=0 anddals=0. DXMS, DXLS areforthelong answer isYesa return ismade totheGetCommand edges ofthe vector anddams, dxlsareforthe endcaps Subroutine 703andthevector isdiscarded. Ifthean- jump isthen made tostep 732SwerisNo,¢jumpismadetostep717andatestismadessiftheanswerinstep729isthattheedgesarenot toseifasingle-width ordouble-width vector isbeing nearly horizontal, jump tostep731andcalculate themade. ValuesfordxmsanddxlsbyuseofaPROMlook-upTriisdouble-width, ajumpismadetothedouble- able.Thecountfortheendcapswillbesetat2*Deltawidth routine 58GeeFIG. 9B).IfNo, jump ismade Y.TheDelt YandDelta Xobtained from thePROMstostep318.Instep718,thecount(CNT)iscomputed, 60isdividedby1wo.which isY2-—YI thentheresult ischecked toseeifit AJump isthenmade tostep732otestforanegative Jszero(0).Irtheanswer isYes,theedgeishorizontal; slope ofthe longsideofthe vector. Ifthe answerisYes,jump ismadetostep719,which iscalled theZontal thesineofDeltaXfound fromthelook-up PROM tablesaebtine Thesubroutine outputs twoedges. Theast ischanged bysubtracting Delta Xfrom zeroin733.A ore 5jumpisthenmadetostep734.Ifthe answer iNoinStep 732, jump tostep 734immediately andoutput the agetV1-4HW,XEHW,0,0) twolongedgesofthevector.The¥valueforthefrstofthetwo long edges isY1+Delta Y.The Xvalue is 4,646,075 41 a X1—Delta X.There isthe count number fortheJong numbers forboth endcapsaresettozero. Ajump is tdge (CNT), andthetwoslope numbers fortheJong thenmade tostep732 edge, DXMS andDXLS. Thesecond edgeoutput will Insteps763and76,ifthe answer isNo,got0septerY1_Delta¥.TheXvalueiXt-+DehaX,along_766andperformacalculationtoderivevalvesfortheWiththecount value forthe longedges andthetwo3twolopenumbers dxms anddls)forthe endcap.Theslopenumbersforthelongedges.Ajumpisthenmadecountfortheendcap2*DeltaYisobtainedfromthetosep735, PROM. Jump tostep732. Insep735atestis made toseeifthe count number Theregular mode edges subroutine 740silustratedfortheendcapiszero.IftheanswerisYes,ajumpisinFIG.9C.Instep74.atestismadetoseeifthescanmade tostep724tocomplete theprocessing. Ifthe10mode hasbeensetto2Xor4Xmode. Ifin2Xmode,tnswer isNo,gotstep73640output theTinesegments jump(0step742.Iftheanswer forthetestforscanforthetwoendcaps.Thefirstedgeoutput is41—Delta__™ode is4Xmode,jumpdirectly tostep743.XtDeltaX:thecountfortheendcap(ent)andthe Instep742,thevaluesforXI,YI.X2,andY2aretwoslopenumbersfortheendcap(Gx,dxls).The,,AND’ed(logically),oneaatime,withaconstanttonextedgeoutput isY2—Delta Y;X2+Delta X;the'truncate theleastsignificant bitandthenstoreeach‘countfortheendcapandthetwoslopenumbersforthebackintotheappropriate storagelocation,ic,X1,Y1,tendcap.Ajumpisthenmadetostep724tocomplete 2,andY2.Ajumpisthenmadetostep743.Fe aeieined before, instep 743,atestfsmadeforYI=Y2? iftheanswer“Thesubroutineilstratedin9BwasaccessedfromaqiYestheedgeshorizontalandthesanconverterwillstep717iftheDouble flagwasse. ignoreitandtheedgeisdiscarded. Thesubroutine thenEntering theDouble subroutine atstep786,thecount etufns totheGetCommand routine. Iftheanswer itnumber ofthelongline segments iscalculated asY2- No.jumptostep744,wherestetismade(0seif“YE,Thecountitestedfora0result. YaY22ino,Jumptosep746.IfYesamptosepireanswerisYes,ajmpismadetosep787to25eneeCMnasuty1andV2andalsointer outputtwoedges.Thefirstis: Ajumpisthenmadetostep746.ThecountnumbergetV1-HY, X12HW,0,0) iscomputed instep746,which isY2~Y1. ThetwoSlope numbers (DXLS andDXMS) arethen computed ‘The second edge output is: x» see 2.27.00) pe=ath (AW=vector width) Ajump isthen made tostep 724 a Insep 756 ithe answer toCnt=0isNo,gO0Sepyg,,THeFstisadjustedintotwooutputwordsabe 18or Instep758,testwhetherY1isgreaterthanY2(Y1- ‘Ajumpisthenmadetostep747andatestmadetosee>Y2).Iftheanswer isYes,exchange Y2andY1(step iftheScanmodeis2X.759),X2andX1andcomputeanewcount(CNT) IftheanswerisNo,jumptostep749.Whichisthenew¥2minusthenewYTandjump10Sep4pg/mTea etnerjoe ieaoesy78CEYa)Ne Septyeah aemtn(OLS Trsep700"3istestedtoseeiftisequaltoX2,DMS)atealsodoubledatthispointandajumpis (X1=X2). IftheanswerisYes,jumptostep761andade10step749tooutputanedge.Theedgei: output two edges. The first edge is: 45 EdgesXt,YI,Cot,DXLS,DXMS) Edge(¥1, X14 HW, Crt,0,0) TheCnt,DXLS, DXMS valuesarethosejustcom-puted.A'retumithenmadetotheGetCommand The second edge is: ibroutine 102 ,50 "The SetScan routine 750s illustrated inFIG. 9D. Searee, zim, This routine first examines abitinthe command wordstep780)todetermineifthemodeis2Xor4X.Ifin2X AumpistbenmadeosepttocompetetbecompsSot heSanneasaut heconetnandforuseofsucceedingcardsintheystem,Ifin4X Ttinstep760,theanswertoX1=X2 isNo,jumptos5Made,theSeanmodelagettthe4Xcondition and sep762andcompute theslopenumbers forthelong” thecommand ott(ep79) Jeby: tsapparent thatthe components which form incre- mental form card 212could beprogrammed using any pra at fitable technique toaccomplish thefunctions de-ow 0scribed above. Anexample ofonesuitablesetofmicro- Code instrections which may beused toprogram incre- [ier thisoperation, goto step763andthen 764{0 mental form card 212issetforth inAppendix M.-Ap- determine ithisslope about tobeoutput isvery near pendix Aillustrates 8bitdescription map which refer-horizontalorcloseenoughtohorizontalforourpur-enceseachlineofthemicrocodeofAppendixMtothe poses.65particular location inthemicrocode PROMs Ul4- Tithe answers Yes,goto step768andsetdelta X=0, 2-UI49 andUISI-U183 (seeFIG. 3B)atwhich the Delta ¥HW (ihe value derived from PROM). The microcode isstored. Thus, inorder tomake and use Count fortheendcaps is2*Delta ¥andtheslope incremental form eard 212inaccordance withthepres 4,646,075 a3 “4 ently prefered embodiment ofthepresent invention,‘oneneedonlyconnecttheincremental formcardIC's,§———_______soutinued __‘using thepinconnectionsasshowninFIG.3B,andthen —ALUFUNCTIONXX}_ seesiePROMSUI42U1andUIS1-UI60using ;:;1 FennerectAppendLewhichisencodeainine $02B ft PROMs assetforthinthebitdescription mapofAp-—__HEX__FUNCTION _MNEMONIC pendix AFromtheabove discussion, itwillbeappreciated that 5 Fas RBASthepresent invention provides adataprocessing pipe . ave RXOSiheotemandthoswhichminimiscsthequantiyer 107 YS roa faeconte points need beprocesed andsored, the fed present invention significantly increases processing a R-S RMSspeedandsavesonneeded storage space.Inaddition, 4 ROSSincethepipeline system andmethod ofthepresent 15S masStvcnonPcewescurvesntheformofBeziercontol > Boas vase hepresent invention aso provides adata pro 2 e108aoerecomandmetbedforprocessingees———E——————— X08tone Stresemavons ofsraphcallustrations which canclipthecurved portions ofsuch illustrations toa20 thepipeline system ofthepresent invention usesanum- b ‘ »reBPs microrogrammedciculcardtheaoneces ieeesdataproceingpipeline25———MEXR$MNEMONIC sem andmethod which incteacs provesing speed rr byprocessing control datapoints withsignificant reli- ' 4 5 RSABanceuponsystem hardware, rather thansystem soft 2 og S29 Teraer, thepipeline systemandmethod ofthepres: $ SKRSEZA rot such’ cartes areexploded ino numerous sal 6 3 $ ERraeaceoetcpayThushepresetmvenon|———2—>——>— S22Provides data proce pnaine forasenprocesing datapoints representing agraphical illustration which sSE creioaetiorwhitmetesaly amocth Tagg BasanMize!eventhough theusratonfyenlargedonthe |ONEBISTATIAS watingscreenAltosincetheindividualcontr}points : AFocene bythepipeline ofthe present vention are) _wex "LOAD ¥_venenencoded,thepresentinventionprovidesanautomated “?55 5"wrk series cea whichscapabe ofproducing both oS NEO Sr igure andlinedrawings aspart ofa sage ius. ==) NOT Nore forms without departing from itsspiritoressentialchar-“sFAB FSRF ee Rcnesemodmens sewbecon =f HemseQ FLOP sideredinallrespects onlyasillustrative andnotrestric- AJ 2F=8 FSUFseer eer rths mscnton therefore ingieseg| byiheappended claims rather thanbythefreB0iN8. gg Shactiptce: Alchanges which come within theear _ — eeTuange ofequelency othe claims teTobe TED ANTA PORT ADDRES Ssmased thin thtspe Ee APPENDIX A | Se MICROCODE MACRO DEFINITIONS 8PL4000 ooTHE DEFAULT STATES ARE CIRCLED. ee) 1.y__} ————_ BB Bz BL Bo ALUFUNCTION XX1_ aeSa 4,646,075 45 46 YRAMADDRESSX17 em “srr o “ ° YRAMA3__YRAMAZ YRAMAL YRAMAD STACK WE DEC REGISTER ar RAM WE FUNCTION oo mo Coy READFROMRAMH RI " WRITE TORAM 3 4 Re 0 5 RS a ‘ Re oTH ; ® 3 : RS SEQUENCER RE/ : ® LOAD: SEQR. 0 Rio 15 __BIT_ SEQUENCER REGISTER ENABLE. b Rit 2 LOADDINTOR6 RB © __HOLD CURRENT RCONTENTS \e Ris—_ & Ris 20 mas ——38 axe DIV PROM UPPER/LOWER . SELECT. DIVUPCONDITION LATCH CLK. 23vieFeAS —_HEX_CONDITION LATCHCLOCK_ @ LowaBALE © LATCHCPUCONDITIONS 1 re HALEATEND OF CYCLE 1 HOLD PREVISIONCONDITIONS 0 mae % XRAM OE/ MULTIPLIER CLOCKSXX7_ TeAnbosENAS 2 7 2 (SeeLOWER BUSENABLE) MPYCLEX ——MPYCLK Y.eycikour 35__4_XRAMOE___MPY XFUNCTION_ Lock:MPYX,MPYY,MPYOUT SEL °XRAMLOWERBUS CLK CLK CLK. MULTIPLIER CLocks “NPYxSyour__FUNCTION SEL } USELESS axox eboceNTS) LOWERBUS X 8B LOGK IN INPUT 40 Nor 1 LOWER BUS —-MPYX X =X 0 CLock RESULT our x OO © __Norwat SE —S eee MAYYVOCONTROLNMIO TVLINE LATCH CONTROL XXE ns 2 xu MPY YSEL AL Mey YSEL A0 INLINELATCHLE INLINE LATCH/MPY OF aL vee DUS ENABLE) HOLD. INLATCH 3 HEX MPY¥ FUNCTION ENANLINELA So LOWERBUS-MPYY Le__O£INLINE LATCH CONTROL so Set sk BUS EEETC SEL |YRAMLOWERBUS @Xx «LATCHDATA. SEL} MPYLSBYTE-LOWER Bus ® —_X_ TRANSPARENT TODATA SEL 3-——_CDIVIDE PROM LOWER BUSx@LATCHOE. NOT °LOWERBUS—-MPYY x 1 MULTIPLIER 0 ay YUposteaegs NOT RAM MY SEL @ ° or rs opt Prom rv —— SEL 25 St XRAMWE° BRANCH ADDRESS Xie er rres NAB NAT NAG _NAS NAM NAB NAZ_NAI__NAO 2 ‘STORE DEFAULT YRAM WE JUMP ADDRESS ° 4,646,075 47 48 x= ADDRESSMODIFICATION SELECTX25 36 os cy « CONSTANT MUX SEL START ADDR $2. START ADDR SI_ START ADDER $0 SELECT: CONST 5 SELECT. ADDMOD GuOrven nusEee) —_HEX_STARTADDRMODIFICATION —TE__COSTANT OX 0NUMBEROFPARAMETERS: ser0CONSTANT 1COLOR SEL|) #OFPARAMETER WORDS. 2 MATRIXGen)©NoMa 10flopr @ NOMODIFICATION LOWERBUSENABLEX20_ 1s GLKLENGTHCONTROLX25 24 ss 6 « LowBUSENA?LOWBUSENAILOWBUSENAO CLKLENGTHAt CLKLENGTHAO SELECT. LOWBUS ‘SELECT: CYCLE LENGTH HEX LOWER BUS DRIVER HEX CYCLE LENGTH rr _ 0 20m® 201 20 1 20on2 TwisTER 2 150ns 3 YRAM XCEIVER o tome4 XRAMXCEIVER a] — 5 SECONDARY INPUT NEXTADDRESSPROMCONTROLX24 “ @ o “ NAPROM A3 NAPROM A2 NAPROM Ai NAPROM AO SEQUENCE (See CONDITION MUX SELECT) TRUE CONDITION FALSE CONDITION com.INSTRUC: INSTRUC. PLETE PROM. MNE: TION. INPUT MNE. "TION. DINPUT MNE. PROMADDE_HEX MONIC SOURCESOURCE STACK MONIC_SOURCESOURCE STACK MONIC_ADDR0 UsrM) DMAPPUSHPC IMPSSTKO wSTORESSMIS oT PROM 201 NeXT epc USTORE omep) Dw STORE UMD 3 42 IMeD DuSTORE (NEXT aPC STORE IMDN$ 6 3.NEXT upc STORE Gea) “RG STORE Nine 3 5 4MPR R USTORE NEXT! uc wSTORE IMRN 9ASNEXT ePC|USTORE Gsk>) —"D.SSTORE PUSHPC|NJSDB©6sD DUSTORE PUSHPCNEXT©UPCwSTORE JSDNDD.E> NEXT abc USTORE (RTS) TKO. wSTORE POP Nets F oF RTS STKO USTORE Por NEXT —uFC.USTORE RISNbo8RTS STKOUSTORE POP=JMPD =DuSTORE RD3 1s AIMPD Dew STORE RIS STKO. GSTORE POP moRT 15 1B Isks STKO WSTORE PUSHPC USRR) -RUSTORE PUSHPC SSSR 7 eC IMPR RuSTORE SseD DB USTORE PUSHPC RSD 19 kD NEXT upc MAP MPs) STKO. MAP NIMS 1BPROM PROM 1c @USHN) PC WSTORE PUSHPC MPM) =D MAP. PNM 1D PROM ie _@MPD) DSTORE _POP___NEXT_wPC_ STORE. oN oF. a @ CLK ENAB 8 ENABLE 10 ‘ arr CLOCK ENABLE i a NORMALcLocK XT DONT CARE 1 LOCK MAY HALT WAITINGON10 FS” x 2 anonMOSELECTS cD nNLarcHENAB ‘CONDITION MUXSELECTXFLOAD:COMMAND s°20,2 BirMDLATCH CLOCK 6s GON, COND, COND, coND—BiT_MP LaTcHchoc MUX} MUXS?——MUX'SI—- MUXS0 io)HOLD COMMAND SELECT: CONDI 1 TRANSPARENT TO NEW DATA HEX CONDITION (F3)_MNEMONIC @ FALSE) CFALS 4,646,075 49 50 sortie CONDITION MUX SELECT XT =“ 6 70 a ”COND COND. COND.«COND sg STACK WRDATA ENABMUXS) MUS: —-MUXSt-—MUXS0 ENABLE STACKWRT'SELECT:CONDI err STACKWRITEDATA HEX_CONDITION (F3}_MNEMONIC tower nus--stack Tarr1ZERO-) to) STACKOF/ TATCH 2 NEGATIVE) SION a@ Co 04 wer carrS|Guerre carro “re6STACKFULL CSTKF TMD aT7STAGREMPTY CMD ‘ourCMD OUTPARM. : cremD,“ ° 1s ‘STATUS.CMD,PARM Larch IDPRWD ciRwD nex TUOND,PARTatcH AODPRND ‘cORFD —_ex_ourrurcmp pry_afoe croc T ‘OUTPUTISPARAMETER€ crocmp ccem 2 Ourrutisemp > o PASS THROUGH eor FrTRUE(1) TRUE 20eemnsouencecotnon ae 2 a crv ovtrur cLx. = as ‘CLOCK: OUTCLEa err (GPUOUTPUTCLOCKSTACK PUSH/POP 2NEWDataTo.OUTPUTS Br,STACK FUNCTION ® HOLD OLD OUTPUT —oi ror x0 m7 PcPASS SoSTATUS POCn-RsELEcT x9 as BIT poc malar stl ao a POWER ONCONFIDENCE PASS SELECT: 10 © __NORMAL, Hex INPUT/OUTPUT rro PRIMARY INPUT © 2 SECONDARY OUTPUT VECTOR Hi TEST CONTROL X36i SECONDARY INPUT Py = 7%or" VHITON. 0VHITOFF|VHITMIT STATUS: VHON, VHDON, VEIT ON OFF) HIT” VECTOR HIT TEST CONTROL, STACK INITIALIZE X30 “s 0 1 1CLRHIT&DONESTATUS7gTASERBUTIALIZE200. 10X__SETDONESTATUSSTACK INIT STACK FRAME INIT > 6 &somaintrsr O_O _@NormarIN Bea X=DONT CARE STACK FRAME 0 ieee INmaLize 0 x INITIALIZE STACK @ERO——=—)s uppx INITIALIZE FRAME (ZERO) (X.RAMADDRESSNAW O_O noma T_T Toot oe s 7DIV PROM INENAB SELECT:SINE_ @UPPERBUSLATCH—DIVPROM ‘STACKCLOCKS. 1LOWERBuspivPROM n7 a DIVLATCH CLE STACK CLK STACK FRAME CLK LOAp: DIVLATCH NATE: ‘STKCLE oO (CLKUPPERBUSLATCH ABLE: FRCLK HOLD PREVIOUS DATASTACK FRAME, o -ck CLR. STACK CLK ste? SEL o x INCR/DECR STACK. 6s HOLD: AOS_x fi INCR/DECR FRAME SHIFT BYPRESELECTED AMT © @ __Nonwat @ SHIFT ToBRING FIRST "1TOPOS—O Norman IN SHIFT IN 4,646,075 51 52 ti rocessing geometric figures which arecomposed ofan_—_____sontinued__ Mayofbothlinesandcurves, saidCPUcomputing aRAMADDRESSXXL pluralityofverticesandaleastonesetofcontrolpoints——BT__FUNCTION ___—_for eachfigureinputatsaidworkstationsuchthateachSHSIGN 5.saidlineisdefinedbytwoend-pointverticesandsuch oOser"ZEROS thateachcurveofsaidfigureisdefinedbyasetofsaid 'a control points, andsaidpipeline comprising:tionsairrowiy) Sensforgeometrically transforming anyofsaid 10 transforming means having 8ninput port and ana ™ottpatporeandtheinputportofsidtransforminga means being connected tosaidmeans forsioring AMOUNT OFSHIFT CLK saiddata; ToAD AOS means forclipping any ofsaid vertices orcontrol sir__Funcrion 15 points 10aviewing frustam, said clipping means ERRARRAYANTOrSmmT havinganinputportandanoutputportandthe b _fouwrarvious Data input port ofssidclipping means being connected es othe output portofsaidtransforming means means forgenerating #series ofdata points which to redefine cach curve ofsaid igure interms of Ey Series ofstraight line segments, said generating 6 tmeanshavinganinputporandanoutputportand AMTOfSENETENABLE theinputportofsaid generating means being con- sr runcabkt nected totheoutput portofstdclipping means ENEI 5herebysaidstraightlinesegmentsaregenerated @_AMOUNTOFDENOMINATOR SHIFT onlyaftertheoutputfromsaidclippingmeansof——2__AMOUNTOFDENOMINATOR SHIFT__ Sidclippedverticesandcontrolpoints:andmeans forconverting said lines and curves defining OOORONSTANT ROK CONST? CONSTe CONSTS CONST4 CONST] CONST? CONST! CONSTO = ssid figure to format compatible foroutputting, PERPENDICULAR UPPER/LOWER 40 ‘Said figure onsaid video output device, said con: 2 werting means being connected totheoutput port SaLucr Day *ofsaid generating means.arinerion_ ataprocessingpipelineasdefinedinclaim1 ® ax whereinsaidtransforming meanscomprises: es itr maker circuit having ainput port anda Culput port, said matrix maker circuit comprising means forassembling transformation matrices, $e _=_ammatrit mattipircireit havinganinputportandanyyLPERBUSENABLEXIS outputporttheinputportofsaid matrix multiplier UPPBUSENA2 UPPBUSENAI UPPBUSEN Ao50_circuitbeingconnected tosaidoutputportofthe ex “UPPER BUSDRIVER comprising means forConcatenating twomatrices oO ‘avectormultiplier circuithavinganinputportandan? suereR output port, theinput port ofsaidvector multiplier3 AMOUNT OFSHIFT 58circuitbeingconnected totheoutputportofsaid: PRMAny fhatrit multiplier circuit, said vector multiplier A PERPENDICULARS PROM Gireuit comprising means for transforming. sid i INPUT DATA FORT Wertices and control points byatransformation 60 said matrix maker circuit, matrix multiplier circuit What isclaimed anddesired tobesecured byUnited andvector multiplier circuit each further compris- States Letters Patent i ingmeans forseparately programming each said ‘In acomputer graphics system having aCPU, a _ceuit so.a8 toprovide forgeometric transforma- work station connected tosaid CPU forinputting tons intheform ofrotation, translation, scalingraphicsdatatosaidsystem,meansConnectedfosaid68_andsheartranaformationsEU torstoring saiddata andmeans connected tosaid 3.,A data processing pipeline asdefined inclaim 1 CPU foroutputting graphic illustrations ona.video wherein saidviewing frustum comprises aplurality of Sutput device animproved Gataprocessing pipelin for sides which define theboundaries ofsaidviewing frus- 4,646,075 53 54tumandwhereinsaidclippingmeanscomprises asepa- togenerateasufficient numberofline segments to rateclipping circuit corresponding toeach saidsideof essentially eliminate theappearance ofanystraightséidviewingfrustum,eachsaidclippingcircuithaving lineapproximations inanyofsaidcurves;and‘aninput portandanoutput portandeachsaidclipping means forconverting saidlinesandcurves defining circuit being connected inseries onetotheother and $ saidfigure toaformat compatible foroutputting ‘comprising means forseparately programming each saidfigure onsaidvideo monitor, saidconverting saidcircuit soastosequentially clipsaidvertices and ‘means being connected totheoutput portofsaid ‘control points inaccordance with theboundaries de- generating means. fined bythesides ofsaidviewing frustum. 8.Adataprocessing pipeline asdefined inclaim 7 ‘4.Adata processing pipeline asdefined inclaim 110wherein each saidmeans comprises atleast onecircuit further comprising means, connected inseries between which isseparately programmed such thateach said saidclipping means andsaidgenerating means, forpro- circuit maysimultaneously process saidvertices and jecting saidvertices andcontrol points inperspective control points atthesame timeasoneormore ofthe‘ontoanareawhichcorresponds toatwo-dimensional othersaidcircuitsareprocessing saidverticesandcon-viewingsurfaceofsaidvideooutputdevice. 15trolpoints.'S.Adataprocessing pipeline asdefined inclaim 1 9.Adataprocessing pipeline asdefined inclaim 8 further comprising means, connected totheoutput port further comprising means, connected totheoutput portofsaidtransforming means,forprocessing saidvertices _ofsaidtransforming means,forprocessing saidvertices‘andcontrol points soastogenerate information for andcontrol points soastogenerate information for preparing shaded surfaces ofsaidfigure anddetermin- 20preparing shaded surfaces ofsaidfigure anddetermin-ingwhichsurfacesofsaidfigurearehidden. ingwhichsurfacesofsaidfigurearehidden.%.Adataprocessing pipeline asdefined inclaim 1 10.Adataprocessing pipeline asdefined inclaim 9 wherein each saidtransforming, clipping andgenerat- wherein saidviewing frustum comprises aplurality of ingmeans comprise atleastonecircuit separately pro- sideswhich define theboundaries ofsaidviewing frus- grammed such that each said circuit may simulta- 25tumandwherein saidclipping means comprises asepa~ neously process saidvertices andcontrol points atthe rateclipping circuit comprising means forclipping said‘sametimeasoneofmoreoftheothersaidcircuitsareverticesandcontrolpointstoeachsaidsideofsaidprocessing saidvertices andcontrol points. viewing frustum, each saidclipping circuit having an 7.Inacomputer graphics system having aCPU, a input portandanoutput portandeachssidclipping work station connected tosaid CPU forinputting 30circuit being connected inseries onetotheother and graphics datatosaidsystem, means connected tosaid comprising means forseparately programming each CPU forstoring saiddata, andmeans connected tosaid saidcircuit soastosequentially clipsaidvertices and CPU foroutputting graphic illustrations onavideo control points inaccordance with theboundaries de-monitor,animproved dataprocessing pipelineforpro-finedbythesidesofsaidviewingfrustum.cessinggeometric figureswhicharecomposed ofboth3511.Adataprocessing pipelineasdefinedinclaim8linesandcurves,saidCPUcomputing apluralityofwhereinsaidtransforming meanscomprises:vertices andatleast onesetofcontrol points foreach amatrix maker circuit having aninput port andan figure input atsaidwork station such thateach curve of ‘output port, saidmatrix maker circuit comprisingsaidfigureisdefinedbyasetofsaidcontrolpoints,and ‘meansforassembling transformation matrices;saidpipeline comprising: 40 amatrix multiplier circuit having aninput portandan means forgeometrically transforming anyofsaid ‘output port, theinputportofsaidmatrixmultiplier vertices andcontrol points toanewposition, said circuit being connected tosaidoutput portofthe transforming means having aninput portandan ‘matrix maker circuit, saidmatrix multiplier circuit ‘output portandtheinput portofsaidtransforming ‘comprising means forconcatenating twomatrices; ‘means being connected tosaidmeans forstoring 45 avector multiplier circuit having aninput portand said data; ‘andoutput port,theinputportofsaidvectormulti- means forclipping anyofsaidvertices andcontrol pliercircuit being connected totheoutput portof points toaviewing frustum, saidclipping means ‘saidmatrix multiplier circuit, saidvector multiplier hhaving aninput portandanoutput portandthe circuit comprising means fortransforming said input portofsaidclipping means being connected SO vertices andcontrol points byatransformation totheoutput port ofsaidtransforming means; matrix; and‘meansforprojecting anyofsaidverticesandcontrol saidmatrixmakercircuit,matrixmultiplier circuitpoints inperspective onto anarea which corre ‘andvector multiplier circuit each comprising sponds toatwo-dimensional viewing surface of means forseparately programming each saidcir- saidvideo monitor, saidprojecting means having 5$ cuitsoastoprovide forgeometric transformationsfaninputportandanoutputportandtheinputport, intheformofrotation,translation, scalingand ofsaidprojecting means being connected tothe shear transformations. ‘output portofsaidclipping means; 12.Inadataprocessing pipeline thatclipselectronic means forgenerating aseries ofdatapoints which signals toaviewing frustum, saidelectronic signals re-define each curve ofsaid figure interms ofa60representing vector-valued contro!pointsdefining series ofstraight line segments, said generating curved edgesandcurvedsurfacesofageometricfigure, ‘means having aninput port and anoutput port and asystem comprising:theinputportofsaidgenerating meansbeingcon- _meansforclippingsaidcontrolpointstosaidviewingnectedtotheoutputportofsaidprojecting means, frustum,saidclippingmeanscomprising anoutputwhereby said linesegments aregenerated only 65 port fortransmitting electronic signals represent- after said vertices and control points areclipped ingtheclipped control points; and andprojected bysaidclipping means andsaidpro-_an exploder circuit comprising means forredefining Jjecting means50astoenablesaidgenerating means ‘thecurvededgesandsurfacesdefinedbythe 4,646,075 55 56 clipped control points ascurved edges comprised ‘output portsothatsaidstraight linesegments are ofapluralityofstraightlinesegments andcurved generated onlyaftersaidcontrolpointsaregeo-surfaces comprised ofapluralityofessentiallypla- ‘metricallytransformed, clippedandprojectedonto narpatches, whereby saidstraight linesegments saidviewing surface; and ‘andsaidplanar patches aregenerated only after $anincremental form circuit comprising means for saidcontrol points areclipped. transforming saidstraight linesegments intoafor-13,Adataprocessing pipelineforprocessing ageo- ‘matforscanlineconversion, saidincremental formmetric figure having oneormore curves defined bya circuit alsocomprising anelectronic data input setofvector-valued control points, whereby saidfigure port andanelectronic data output port, theincre- ‘eanbedisplayed inananimated mode using aseries of10 mental form circuit's input portbeing electroni- geometric transformations, saidpipeline comprising: cally connected totheexploder circuit's output ‘amatrix maker circuit comprising means fordefining, portandsaidincremental form circuit's output portatleastonematrixforeachsaidgeometric transfor- beingconnected toameansfordisplaying said‘mation, saidmatrix maker circuit alsocomprising graphic illustration, whereby said figure isdis- fanelectronic data input port forreceiving said 15 played inananimated mode.‘controlpointsandanelectronic dataoutputport; 14,Amethodofgenerating ageometric figurewithin‘amatrix multiplier circuit comprising means forcon- theboundaries ofaviewingfrustum,saidmethodcom- ‘catenating atleast two ofthematrices defined by prising thesteps of: Said matrix maker circuit, said matrix multiplier transmitting toaCPUfromadatainputdeviceaset Circuit alsocomprising anelectronic data input 20 ofelectronic signals representing saidfigure;portandanelectronic dataoutputport,thematrix_transforming saidelectronic signalsintoafirstsetofmultiplier circuitinputportbeingelectronically ‘controlpointsrepresenting saidfigure,saidcontrol ‘connected tothematrix maker circuit output port; points comprising both vertices terminating said‘aheadercircuitcomprising meansforgenerating linearedgesofsaidfigureandparametric controlcommand signals forcontrolling each circuit of25 points corresponding tosaidcurved edge ofthe saiddata processing pipeline assaidcircuits are figure; usedtoprocess saidcontrol datapoints, saidheader _clipping saidfirstsetofcontrol points suchthatsaid circuit alsocomprising afirstelectronic datainput vertices andparametric control points arewithin portforreceiving saidcontrol points andafirst theboundaries ofsaidviewing frustum, thereby electronic dataoutput port; 30 generating asecond setofcontrol points compris- vector multiplier circuit comprising means forgeo {ngthevertices andparametric control points re- ‘metrically transforming said control points, said ‘maining after saidclipping step; and vector multiplier circuit alsocomprising afirst’ transmitting saidsecond setofcontrol points toa electronic data input port which iselectronically video output devicesoastoillustratesaidfigureat connected tothefirst header circuit output port, a35 saidvideo output device. second electronic datainput portwhich iselectron-_18, Amethod asdefined inclaim 14wherein trans- ieally connected tothematrix multiplier circuit forming stepcomprises generating anelectronic code output port,andafirstelectronic dataoutput port; associated witheachcontrol point, saidcodespecifi-apluralityofclipper circuits, eachsaidclipper circuit cally identifying theparametric control points ofsaid ‘comprising means forclipping saidcontrol points 40curved edge. todifferent clipping planes fromoneanother, said 16.Amethod asdefined inclaim 14wherein said clipping planes defining aviewing frustum, and clipping stepcomprises successively clipping saidfirst saidclipper circuits eachcomprising anelectronic setofcontrol points toeachsideofsaidviewing frus- data input port and anelectronic data output port, tum, theinput portofatleastonesaidclipper circuit 43 17.Amethod ofgenerating geometric figure within being electronically connected tothefirstoutput theboundaries ofaviewing frustum, saidmethod com- portofsaidvector multiplier circuit andsaidclip- prising thesteps of: percircuits being electronically connected inseries. transmitting toaCPU from adatainput device aset conewith another such thatcontrol points transmit- ofelectronic signals representing saidfigure; tedtoafirstclipper circuit arethensequentially 50transforming saidelectronic signals intoafirstsetof clipped inturnbyeachoftheremaining clipper ‘control points representing saidfigure, saidcontrol circuits, withthefullyclipped control points being points comprising bothvertices terminating linear‘outputfromtheoutputportofthelastclipper edgesofthefigureandcontrolpointscorrespond- circuit;ingtocurved edges ofthefigure; 1view portcircuit comprising means forprojecting $5 clipping saidfirstsetofcontrol points whereby a ‘saidcontrol points inperspective ontoanarearep- second setofcontrol points isgenerated represent- resenting atwo-dimensional viewing surface, said ingthefigure afterithasbeenclipped tofitwithin, viewportcircuit alsocomprising anelectronic data theboundaries ofsaidviewing frustum; input portandanelectronic dataoutput port, the generating from saidsecond setofcontrol points a inputportofsaidviewportcircuit being electroni- 60 plurality ofelectronic signals which redefine each callyconnected tosaidlastclipper circuits output curved edge ofsaidclipped figure interms ofaport; seriesofsmallstraightlinesegments; andanexplodercircuitcomprising meansforredefining _transmitting saidelectronic signalstoavideooutputsaid curves interms ofapluralityofsmallstraight devicesoastoillustratesaidfigureatsaidvideo linesegments,saidexplodercircuitalsocomprising65_outputdevice. ‘anelectronic datainputportandanelectronic data ‘18.Amethodasdefinedinclaim17whereintrans-‘output port, theexploder circuit input portbeing forming stepcomprises generating afirstelectronic electronically connected totheview portcircuit's code associated witheachcontrol point, saidfirstcode 4,646,075 37 58 specifically identifying thecontrol points ofeachsaid tiveontoanareaofatwo-dimensional viewingsurface curvededge Whichcorrespondstoaportionofsaidvideomonitor. 19.Amethodasdefinedinclaim17whereinsaid.24,Amethodavdefinedinclaim22furthercompris, clippingstepcomprisessuccessively clippingsaidfirst,iR&thestepsofprocessingsaidcontrolpointssoas patercsivelyclippingsaidFst”generateinformationforpreparingshadedsurfacesof e#controlpointstoeachsideofsaid 1gfrus-“Saidfigureanddetermining whichsurfacesofsaidfig-um. urearehidden. 20,Amethod a8defined inclaim 18wherein ssid “S3"Ta"s Csmputer graphics system havingaCPU, transforming step comprises generatingasecondelec-workstationconnectedtosaidCPUforinputting troniccodeassociatedwitheachcontrolpoint,said10graphiosdatatosaidsystem,meansconnectedtosaid second code indicating whether anassociated edge of CPU forstoring said data, and means connected t0said saidfigure istoberendered asalinedrawing. CPU foroutputting sequential video frames represent-21.Amethodasdefinedinclaim20whereinsaidinganimatedgraphicillustrationsonavideomonitor,8 ‘generating stepcomprisesenlargingsaidstraightTinemethodofprocessing geometric figures which arecom- segments soastoformthinrectangles therefrom for15posed ofbothlinear andcurved edges, saidmethodrendering portions ofsaidfigure asalinedrawing, comprising thestepsof:‘Computing atleastonesetofcontrolpointsforeach 22,In-acomputer graphics systemhavingaCPU,a figureinputatsaidworkstationsuchthateach ‘workstationconnected tosaidCPUforinputting fgarenetataaeaoyaidcontolgraphics datatosaidsystem, means connected tosaid45CPUforstoring saiddata,andmeansconnected tosaid Laue)geometrically transforming eachsetofcontrolpoints CPUforoutputting graphicillustrations onavideo ‘ovanewpositionforeachsaidvideoframe;monitor, amethod ofprocessing geometric figures clipping saidcontrol points toaviewing frustum; Which arecomposed ofboth linear andcurved edges, projecting saidcontrol points inperspective onto an saidmethod comprising thesteps of: 25 area ofatwo-dimensional viewing surface which‘generating atleastonesetofcontrolpointsforeach corresponds 0aportionofsaidvideomonitor;figure input atsaidwork station suchthateach redefining eachcurve ofsaidfigure interms ofa ccurve ofsaidfigure isdefined bysaidcontrol seriesofstraightlinesegmentswhicharegenerated‘ ‘onlyaftersaidcontrol points areclipped andpro- °nt: outputting “saidfigure onsaidvideo monitor, 1anew position foreach said video frame;‘ whereby saidfigurewillbeoutputonsaidvideo clipping said control points toaviewing frustum;clip ‘ nso a ‘monitor inananimated modeofdisplay.lefiningeachcurveofsaidfigureintermsof@26.4methodasdefinedinclaim25furthercompris- seriesofstraight linesegments which aregenerated 35ingthestepofprocessing saidcontrol points 30a510 only after sadcontrol points aeclipped; and {generate information forpreparing shaded surfaces ofoutputting saidfigureonsaidvideomonitor. Sidfigureanddetermining whichsurfacesofsaidfig-23,Amethod asdefined inclaim 22further compris- ureare hidden. ingthestepofprojecting saidcontrol points inperspec: trees 0 4s 0 ss © “6s UNITED STATES PATENT AND TRADEMARK OFFICE CERTIFICATE OF CORRECTION PATENT NO. 4,646,075 DATED February 24, 1987 INVENTOR(S) DavidH.Andrews etal. Itiscertified thaterrorappears intheabove—identified patent andthatsaidLetters Patent arehereby corrected asshown below: Onthe title page, second inventor should read--Philip H.Lucht --. Abstract, line 5,"are" should be--is-- . Abstract, line 35, "are" should be--is-~ Column 1,line 14, “are” should be--is-- Column 5,lines 17-18, "inadesirable feature." should be --is adesirable feature.-- Column 8,line 54, "wll" should be--will-~ Column 10, line 46, "pipline" should be--pipeline-- Column 11, line 30, "storage" should be--store —- Column 12, line 33, "against" should be--again-- Column 22, line 28, "thaw" should be --than-~ Column 22, line 36, "are enter" should be--enter-- | Column 23, line 61, "off" should be--of-- | Column 29, line 62, "step 522" should be--step 523-- Column 33, line 28, "as" should be --is—- Column 36, line 30, "is then" should be--and isthen-~ Column 38, line 30, "211 211" should be--211-- Column 38, line 35, "on order" should be--in order-- Column 39, line 29, "are" should be --is-- Column 41, line 12, "41" should be --¥1-~ Signed and Sealed this Nineteenth Day ofJanuary, 1988 Autest: DONALD 1.QUIGG AnestingOfficer Commissioner ofPatentsandTrademarks