– Vi la siste hånd på den første vitenskapelige artikkelen om Oslo-algoritmen i juni 1979 og så var vi veldig stolte da artikkelen ble antatt og publisert året etter. Det er jo hyggelig å tenke på at i dag sitter hele verden og ser på sånne ting som vi jobbet med, forteller professor emeritus Tom Lyche ved Matematisk institutt på UiO.

Han snakker om de glatte og fine bokstavene som fyller dataskjermer over hele verden. De som har levd en stund, husker at bokstavene på dataskjermene i gamle dager var hakkete og stygge, men så skjedde det noe på 1980-tallet. Da kom programmeringsspråket Postscript, som blant annet gjorde det mulig å tegne glatte og fine bokstaver i alle mulige størrelser.

– Jeg vil ikke akkurat si at Oslo-algoritmen direkte ligger inne i alle moderne fonter. Men programvaren som lager fontene, bygger på den samme filosofien som du finner i Oslo-algoritmen, presiserer Lyche.

Her er det på plass med en liten ordforklaring: En algoritme er en regneregel, en matematisk oppskrift på hvordan et eller annet skal beregnes. Du bruker en enkel algoritme når du dividerer et flersifret tall, og Skatteetaten bruker en litt mer komplisert algoritme når de regner ut skatten din på grunnlag av inntekten og fradragene.

– Oslo-algoritmen er en regneregel som gjorde det mulig å tegne kurver og former akkurat slik du ønsker at de skal være. Du kan starte med noen enkle polynomer som gir deg en glatt og sammenhengende kurve og så kan du endre kurvens form ved hjelp av Oslo-algoritmen. Resultatet blir fortsatt en glatt kurve, forklarer Lyche.

Begrepet polynom er nærmere forklart i faktaboksen under.

Åpnet døren for DAK/DAP

Bakgrunnen for Oslo-algoritmens suksess er at den kan brukes til mye mer enn å tegne linjer, kurver og flater. De ferdige tegningene kan nemlig blant annet brukes til å styre fresemaskiner, sveiseroboter og slike ting. Da er vi plutselig over i det som blir kalt DAK/DAP – dataassistert konstruksjon og produksjon – og Oslo-algoritmen brukes fortsatt i stort omfang på dette feltet. Til bildesign, flydesign, arkitektur, karttegning, turbinproduksjon, skipsbygging og så videre.

Varianter av Oslo-algoritmen ligger også bak kameraføringen og tegningen av figurene i den banebrytende animasjonsfilmen Toy Story.

– Det amerikanske tegnefilmstudioet Pixar gikk senere over til en annen og mer grafisk teknikk, men spline-kurver og Oslo-liknende algoritmer brukes fortsatt i andre tegnefilmer, forteller forskningsleder Tor Dokken ved Sintef Digitals avdeling for matematikk og kybernetikk. En spline er en funksjon som er stykkevis definert av ulike polynomer.

– Da Oslo-algoritmen kom for 40 år siden, var det akkurat til rett tid når det gjaldt datamaskinenes utvikling og behovet i industrien. Det hadde pågått en kamp om å utvikle den rette algoritmen, men Oslo-algoritmen ble stående som den riktige måten å gjøre det på. Dette var algoritmen som virkelig gjorde datamaskin-assistert konstruksjon og –produksjon mulig, tilføyer Dokken.

Han forteller at Oslo-algoritmen fikk stor betydning for det som nå er matematikk og kybernetikk-avdelingen ved Sintef Digital.

– Det var et helt grunnleggende numerisk verktøy som da kom på plass og som ga oss en mulighet til å få store prosjekter og jobbe med anvendelser. Algoritmen la et grunnlag for at vi lyktes kommersielt med programvare som bruker splines mot industrien. Og 40 år senere har vi fortsatt bra med aktiviteter på dette området. I alle disse årene har vi hatt et godt og tillitsfullt samarbeid med Tom Lyche og miljøet på UiO, forteller Dokken.

Algoritmens forhistorie

Tom Lyche (født 1943) begynte å studere matematikk ved UiO i 1964. Han fullførte en hovedfag (cand.real.) i Oslo og reiste deretter til USA for å ta en doktorgrad ved University of Texas. Der kom han i kontakt med Larry Schumaker, som veiledet ham fram til en doktorgrad i spline-teori. Forskerne som jobber med dette, bruker forresten helst den engelske flertallsformen splines, av forståelige årsaker.

I 1972 ble Lyche ansatt som universitetslektor i numerisk analyse ved Institutt for informatikk, mens han var i ferd med å skrive ferdig doktorgraden. Han etablerte også et hovedfagskurs, som etter hvert fikk mange dyktige hovedfagsstudenter. En av disse var Tor Dokken, som ble ferdig i 1978 og straks fikk jobb på Senter for industriforskning (SI) – som senere gikk inn i forskningsstiftelsen Sintef. Der er han fortsatt, som en ivrig bruker av splines og Oslo-algoritmen.

– På SI ble jeg med i en gruppe som skulle jobbe med å modellere form, og en dag kom det amerikanske forsker-ekteparet Elaine Cohen og Richard Riesenfeld fra University of Utah på besøk. De hadde hørt om Tom og ville gjerne møte ham, så da ble det til at jeg fulgte dem ned til kontoret hans, minnes Dokken.

Amerikanerne var interessert i å bruke spline-funksjoner til å modellere fysiske objekter, og de etablerte senere et firma som brukte både splines og Oslo-algoritmen til å designe og frese ut fysiske objekter. De hadde allerede skrevet en vitenskapelig artikkel om splitting og skjøting av kurver, som er grunnlaget for arbeidet med splines. Men de ante at det måtte finnes en mer effektiv måte å gjøre dette på og at Lyche var mannen som kunne løse problemet – og det stemte.

– Tom var en veldig god teoretisk spline-matematiker, etter min mening blant de beste i verden. Jeg tror ikke han hadde tenkt så mye på at teoriene hans kunne ha praktisk verdi, men så viste det seg altså at Oslo-algoritmen gikk rett inn i et industrielt behov, forklarer Dokken.

Matematisk teori til praktisk bruk

Polynomer med tilstrekkelig høy grad kan i prinsippet tegne veldig kompliserte kurver. Men polynomer av høy grad har også noen ulemper, så hvis du vil kunne tegne generelle kurver uten disse ulempene, må du finne på noe annet – og det var det Tom Lyche og kollegene gjorde med Oslo-algoritmen.

– Du trenger ikke forstå matematikk for å glede deg over Toy Story eller et digitalt tegneprogram. Men det ligger veldig mye matematikk bak disse produksjonene, selv om folk flest kan bruke dem uten å tenke på matematikk i det hele tatt, sier professor Knut Mørken.

Han tok sitt hovedfag i matematikk med Lyche som veileder, og han har senere hatt stor glede av Oslo-algoritmen i en karriere som i dag har gjort ham til visedekan for utdanning ved MN-fakultetet.

Ideen bak splines og Oslo-algoritmen er tilsynelatende enkel: Det er ikke nødvendig å bruke veldig kompliserte polynomer for å tegne en komplisert kurve; du kan isteden dele opp kurven i mange småbiter og beskrive hver enkelt bit med enklere polynomer. Det Oslo-algoritmen gjør, er å skjøte sammen biter av polynomer på en enkel og effektiv måte.

– Du kan for eksempel bruke ett tredjegradspolynom på det ene intervallet og et annet tredjegradspolynom på neste intervall. Og så videre. Det unike med Oslo-algoritmen er at den håndterer dette samtidig som den kan «oversette» noe som er tegnet på en grov skala til en fin skala uten å endre på beskrivelsen. Dette har vist seg å være veldig slagkraftig, forteller Mørken.

Richard Riesenfeld hadde allerede skrevet en algoritme for å gjøre dette, men den hadde begrensede muligheter. Hans algoritme førte til at det var nødvendig å sette inn nye biter overalt i polynomet, selv om det bare var en detalj som skulle endres. Dermed ble det matematiske uttrykket veldig stort og uhåndterlig.

– Da Elaine og Rich kom inn på mitt kontor i 1979, ønsket de å kunne gjøre dette lokalt. Det høres kanskje banalt ut, men det var ikke så lett å få til. Poenget med Oslo-algoritmen er at polynomene blir representert på en spesiell måte; vi brukte noe som heter B-splines, som altså følger ett polynom til et nytt polynom overtar. To spline-kurver som møtes får samme verdi og tangent i møtepunktet og da får vi en helt glatt kurve som kan skaleres opp og ned, forklarer Lyche.

Bygde på tidligere kunnskap

Tom Lyche er en beskjeden mann som er opptatt av å løfte fram dem som hadde lagt grunnlaget for den matematiske utviklingen av Oslo-algoritmen. På Akers Mekaniske Verksted brukte de for eksempel fysiske modeller av splines for å lage de formene som skulle brukes i skipsbyggingen. De fysiske modellene var store, bøyelige metallstenger, en slags linjaler og så brukte skipsbyggerne lodd av ulik vekt for å bøye stengene til den formen de ville ha.

Det er også på sin plass å nevne Even Mehlum, som lagde det hullkortbaserte programmet Autokon allerede i 1965. På Kongsberg Våpenfabrikk hadde de tegnemaskiner som kunne tegne sirkler og rette linjer, og Mehlums system gjorde at disse kunne tegnes ut veldig fort. Autokon var så vellykket at systemet på et tidspunkt hadde hele 70 prosent av verdensmarkedet for modellering av skipsskrog, forteller Lyche.

Den franske matematikeren Joseph Fourier begynte så smått å utvikle den nødvendige teorien allerede på 1700-tallet, da han viste at alle periodiske funksjoner kan framstilles som en sum av sinus- og cosinusfunksjoner. Den moderne utviklingen startet under annen verdenskrig, da den rumensk-amerikanske matematikeren Isaac Jacob Schoenberg arbeidet med nøyaktig tabulering og glatting av data som beskrev en bombekasterbane.

På 1960-tallet begynte de franske bilfabrikkene Renault og Citroën å bruke datamaskiner til å modellere bilkarosserier. Citroën-matematikeren Paul de Fajet de Casteljeau og Renault-ingeniøren Pierre Bézier har skrevet seg inn i matematikk-historien fordi de utviklet et spesialtilfelle av spline-funksjonene for å få til dette.

Det hører også med til historien at en tysk kollega av Lyche, Wolfgang Böhm, omtrent samtidig utviklet en alternativ variant av Oslo-algoritmen.

Studenter har gjort karriere

Tom Lyche har hatt mange studenter som senere har gjort karriere, i tillegg til Tor Dokken og Knut Mørken. Også MN-fakultetets dekan Morten Dæhlen har studert hos Lyche.

– Jeg vært velsignet med mange gode studenter, og Ragnar Winther var faktisk min første hovedfagsstudent. Han har nettopp avsluttet et stort EU-prosjekt, forteller Lyche.

– Hvis ikke Tom Lyche og de to amerikanerne hadde funnet opp Oslo-algoritmen, måtte noen andre gjort det. Den kan forresten også brukes til å komprimere lydfiler og bilder ned til minst en tidel av størrelsen, uten at du hører eller ser noen særlig forskjell. I USA bruker politiet fortsatt dette til å komprimere fingeravtrykk, sier Knut Mørken.

Glemte seg og havnet i Drammen

Tom Lyche er 75 år gammel, men har ingen planer om å pensjonere seg. Isteden kommer han fortsatt til kontoret sitt i 12. etasje i Abels tårn – den såkalte emeritus-etasjen – hver eneste dag, unntatt i feriene og når han er på en internasjonal konferanse. Det er sånn det blir med folk som elsker jobben sin. Matematikere kan nemlig bli veldig engasjert i det de holder på med.

– I miljøet vårt forteller vi fortsatt om første gang Stanford-professoren Donald Knuth var i Oslo, da jobbet han med å lage digitale fonter. Tom og Donald skulle spise middag hos Ole Johan Dahl i Asker, og Tom skulle kjøre. Men underveis ble de så engasjert i en matematisk diskusjon at de glemte avkjøringen til Asker. De oppdaget ingenting før de var kommet helt til Drammen, så den middagen ble litt forsinket, forteller Knut Mørken.

Den første vitenskapelige artikkelen om Oslo-algoritmen:

Elaine Cohen, Tom Lyche og Richard Riesenfeld: Discrete B-splines and subdivision techniques in computer-aided geometric design and computer graphics. Computer Graphics and Image Processing, 1980. (Sammendrag)

Artikkelen er produsert og finansiert av Universitetet i Oslo

Universitetet i Oslo er én av 77 eiere av forskning.no. Deres kommunikasjonsansatte leverer innhold til forskning.no. Vi merker dette innholdet for å tydelig skille formidling fra uavhengig redaksjonelt stoff.
Her kan du lese mer om ordningen.

Fikk du med deg disse artiklene fra Universitetet i Oslo?

Hummerens sexliv skaper rom for større reservater

Proteiner avslører kreftsvulstens hemmeligheter

Derfor gjør kunstig intelligens fortsatt enkle feil vi mennesker aldri ville gjort