MIT-forskare har utvecklat en teknik som "reverse engineer" komplexa 3D-modeller med datorstödd design (CAD), vilket gör dem mycket lättare för användare att anpassa för tillverkning och 3D-utskriftsapplikationer.

Nästan alla kommersiella produkter börjar som en CAD-fil, en 2-D eller 3-D modell med produktens designspecifikationer. En metod som ofta används för att representera dagens 3D-modeller är konstruktiv solid geometri (CSG), en teknik där många grundläggande former, eller "primitiver, " med några få justerbara parametrar kan sättas ihop på olika sätt för att bilda ett enda objekt. När det är klart, det kompilerade digitala objektet konverteras till ett nät av 3D-trianglar som definierar objektets form. Dessa nät används som indata för många applikationer, inklusive 3D-utskrift och virtuell simulering.

Anpassa det nätet, dock, är ingen lätt uppgift. Till exempel, justering av radien i en del av objektet kräver individuell justering av hörnen och kanterna på varje påverkad triangel. Med komplexa modeller som består av tusentals trianglar, anpassning blir skrämmande och tidskrävande. Traditionella tekniker för att omvandla triangelmaskor tillbaka till former kan inte skalas bra till komplexa modeller eller fungerar exakt med låg upplösning, bullriga filer.

I ett dokument som presenterades vid den nyligen genomförda AMC SIGGRAPH Asia-konferensen, MIT-forskare beskriver ett system som använder en teknik som kallas "programsyntes" för att bryta ner CAD-modeller till sina primitiva former, såsom sfärer och kuber. Programsyntes konstruerar automatiskt datorprogram baserat på en uppsättning instruktioner.

Väsentligen, att bygga CAD-modeller, designers sätter ihop individuella former till ett slutligt objekt; forskarnas metod gör det omvända, demontering av CAD-modellerna till individuella former som kan redigeras. Som input, systemet tar ett 3D-triangelnät och bestämmer först de individuella former som utgör det. Programsyntes kryper genom formerna, försökte ta reda på hur formerna sattes ihop och sattes ihop till den slutliga modellen. Genom att göra så, det bryter ner nätet till ett träd av noder som representerar de primitiva formerna och andra noder som beskriver stegen för hur dessa former passar ihop. De slutliga formerna innehåller redigerbara parametrar för användarna att justera som kan laddas upp igen till mesh.

Grundläggande former

Forskarna byggde en datauppsättning av 50 3-D CAD-modeller av varierande komplexitet. I experiment, forskarna visade att deras system kunde omvända CAD-filer som består av upp till 100 primitiva former. Enklare modeller kan brytas ner på cirka en minut. Även om körtiderna kan vara snabba, den viktigaste fördelen med systemet är dess förmåga att destillera mycket komplexa modeller till enkla, grundläggande former, säger forskarna.

"På hög nivå, problemet är reverse engineering av ett triangelnät till ett enkelt träd, " säger Tao Du, en Ph.D. student i Computational Fabrication-gruppen vid MIT:s Computer Science and Artificial Intelligence Laboratory (CSAIL). "Helst, om du vill anpassa ett objekt, det skulle vara bäst att ha tillgång till de ursprungliga formerna – vilka dimensioner de har och hur de kombineras. Men när du väl kombinerar allt till ett triangelnät, du har inget annat än en lista med trianglar att arbeta med, och den informationen går förlorad. När vi återställer metadata, det är lättare för andra att ändra design."

Processen kan vara användbar vid tillverkning eller i kombination med programvara för 3D-utskrift, säger Du. Detta är särskilt viktigt i en ålder av designdelning, där amatöranvändare av 3D-skrivare laddar upp 3D-printmodeller till webbplatser för onlinegemenskaper att ladda ner och ändra. Uppladdningar är mestadels triangelnät, eftersom mesh är mycket mer universellt accepterat över plattformar än de ursprungliga CSG-baserade CAD-filerna.

"Vi har massor av mesh-modeller, men jämförelsevis få CAD-filer bakom dem, " Du säger. "Om användare vill reproducera designen hemma och anpassa den lite, då kan den här tekniken vara användbar."

Träd och trianglar

Programsyntes hittar automatiskt kandidatprogram som ges en specifik "grammatik, " vilket betyder strukturen den måste fungera inom, som träd, och matematiska specifikationer. Genom att använda dessa begränsningar, programsyntes arbetar sig tillbaka och fyller i tomrummen för att konstruera en algoritm som uppfyller dessa specifikationer, fått ny input. Tekniken används, till exempel, för enkla komponenter inom mjukvaruutveckling.

I forskarnas arbete har grammatiken är CSG, representeras som träd. Varje slutlig nod (utan förgreningsnoder) representerar en primitiv form med tydligt definierade parametrar, och mellannoder representerar grundläggande sätt som formerna konvergerar och relaterar.

Forskarna utvecklade en metod som låter programsyntes skanna ett helt 3D-nät och, väsentligen, tänk på varje möjligt CSG-träd som det skulle kunna skapa som ett nytt kandidatprogram.

Efter att systemet tagit emot ett inmatningsnät, ett förbearbetningssteg upptäcker möjliga platser, orienteringar, och parametrar för alla primitiva former. Denna process skapar ett massivt punktmoln över ytan av triangelnätet. En speciell "primitiv-detektion"-algoritm härleder från dessa punkter dimensionerna för varje primitiv form som utgör nätet.

Forskarna provar sedan massor av punkter i hela 3D-utrymmet och flaggar dem som antingen inuti eller utanför nätet. Detta hjälper till att avgöra hur formerna konvergerar eller relaterar till varandra. Ett enkelt exempel är ett nät som består av två sfärer, A och B, slogs samman. Om en samplade punkt faller inuti sfär A, en inuti sfär B, och en i skärningspunkten mellan de två (inuti både A och B), det är troligen en förening av de två formerna.

Med tanke på denna information, tillsammans med de primitiva dimensionerna, programsyntes skulle potentiellt kunna skapa ett CGS-träd. Men, 3D-nät med till och med låg komplexitet skulle kräva programsyntes för att sampla tiotusentals punkter. Detta skulle skapa ett enormt sökutrymme som är beräkningsmässigt opraktiskt att hantera. "Att mata alla proverna direkt kommer att kväva programsyntesen, " säger Du.

För att säkerställa att systemet fungerar effektivt, forskarna designade en samplingsmetod som skapar flera små delmängder av punktprover över 3D-utrymmet, vilket är mycket lättare att beräkna för programsyntes. Genom att ta ett urval av dessa delmängder, det skapar ett nytt kandidatprogram, " eller CGS-träd, som kan anses korrekt. Efter många iterationer – och med hjälp av tekniker för att eliminera vissa punkter och träd – landar systemet på rätt CGS-träd för varje form, med korrekta mellansteg och slutparametrar. Eventuella redigerade former matas tillbaka till nätet när systemet beräkningsmässigt följer de mellanliggande stegen tillbaka till det slutliga objektet.

För närvarande, systemet hanterar bara fyra primitiva former – sfärer, cylindrar, kuboider, och tori (munkformer). Nästa, forskarna strävar efter att öka komplexiteten i CSG-grammatik för att hantera fler former och fler modifierare utanför bara booleska operatorer.

Den här historien återpubliceras med tillstånd av MIT News (web.mit.edu/newsoffice/), en populär webbplats som täcker nyheter om MIT-forskning, innovation och undervisning.