MIT-onderzoekers hebben een techniek ontwikkeld die complexe 3D-computer-aided design (CAD)-modellen "reverse engineers" maakt, waardoor ze veel gemakkelijker voor gebruikers kunnen worden aangepast voor productie- en 3D-printtoepassingen.

Bijna alle commerciële producten beginnen als een CAD-bestand, een 2D- of 3D-model met de ontwerpspecificaties van het product. Een methode die veel wordt gebruikt om de 3D-modellen van vandaag weer te geven, is constructieve vaste geometrie (CSG), een techniek waarbij tal van basisvormen, of "primitieven, " met een paar instelbare parameters kan op verschillende manieren worden samengevoegd tot een enkel object. Wanneer voltooid, het gecompileerde digitale object wordt geconverteerd naar een netwerk van 3D-driehoeken die de vorm van het object bepalen. Deze meshes worden gebruikt als input voor veel toepassingen, inclusief 3D-printen en virtuele simulatie.

Dat gaas aanpassen, echter, is geen gemakkelijke taak. Bijvoorbeeld, om de straal in een deel van het object aan te passen, moeten de hoekpunten en randen van elke betrokken driehoek afzonderlijk worden aangepast. Met complexe modellen bestaande uit duizenden driehoeken, maatwerk wordt ontmoedigend en tijdrovend. Traditionele technieken om driehoekige mazen terug in vormen om te zetten, schalen niet goed naar complexe modellen of werken niet nauwkeurig bij lage resolutie, luidruchtige bestanden.

In een paper gepresenteerd op de recente AMC SIGGRAPH Asia-conferentie, MIT-onderzoekers beschrijven een systeem dat een techniek genaamd "programmasynthese" toepast om CAD-modellen op te splitsen in hun primitieve vormen, zoals bollen en kubussen. Programmasynthese construeert automatisch computerprogramma's op basis van een reeks instructies.

Eigenlijk, CAD-modellen bouwen, ontwerpers assembleren individuele vormen tot een definitief object; de methode van de onderzoekers doet het omgekeerde, het demonteren van de CAD-modellen in individuele vormen die kunnen worden bewerkt. Als invoer, het systeem neemt een 3D-driehoekig gaas en bepaalt eerst de individuele vormen waaruit het bestaat. Programmasynthese kruipt door de vormen, proberen te achterhalen hoe de vormen in elkaar werden gezet en tot het uiteindelijke model werden samengevoegd. Daarbij, het splitst het netwerk op in een boom van knooppunten die de primitieve vormen vertegenwoordigen en andere knooppunten die de stappen beschrijven voor hoe die vormen in elkaar passen. De uiteindelijke vormen bevatten bewerkbare parameters die gebruikers kunnen aanpassen en die opnieuw naar de mesh kunnen worden geüpload.

Fundamentele vormen

De onderzoekers bouwden een dataset van 50 3D CAD-modellen van verschillende complexiteit. Bij experimenten, de onderzoekers toonden aan dat hun systeem CAD-bestanden van maximaal 100 primitieve vormen kon reverse-engineeren. Eenvoudigere modellen kunnen in ongeveer een minuut worden afgebroken. Hoewel de looptijden snel kunnen zijn, het belangrijkste voordeel van het systeem is de mogelijkheid om zeer complexe modellen te distilleren tot eenvoudige, fundamentele vormen, zeggen de onderzoekers.

"Op een hoog niveau, het probleem is reverse engineering van een driehoekig netwerk in een eenvoudige boom, " zegt Tao Du, een doctoraat student in de Computational Fabrication-groep van MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL). "Ideaal, als u een object wilt aanpassen, het zou het beste zijn om toegang te hebben tot de originele vormen - wat hun afmetingen zijn en hoe ze worden gecombineerd. Maar als je alles eenmaal combineert tot een driehoekig netwerk, je hebt niets anders dan een lijst met driehoeken om mee te werken, en die informatie gaat verloren. Zodra we de metadata hebben hersteld, het is gemakkelijker voor andere mensen om ontwerpen aan te passen."

Het proces kan nuttig zijn bij de productie of in combinatie met 3D-printsoftware, zegt Du. Dit is vooral belangrijk in het tijdperk van het delen van ontwerpen, waar amateur-3D-printergebruikers 3D-printmodellen uploaden naar websites die online communities kunnen downloaden en wijzigen. Uploads zijn meestal driehoekige mazen, omdat meshes veel universeler worden geaccepteerd op verschillende platforms dan de originele CSG-gebaseerde CAD-bestanden.

"We hebben tonnen mesh-modellen, maar relatief weinig CAD-bestanden erachter, ", zegt Du. "Als gebruikers het ontwerp thuis willen reproduceren en een beetje willen aanpassen, dan kan deze techniek nuttig zijn."

Bomen en driehoeken

Programmasynthese vindt automatisch kandidaat-computerprogramma's met een specifieke "grammatica, " wat betekent de structuur waarbinnen het moet werken, zoals bomen, en wiskundige specificaties. Met behulp van die beperkingen, programmasynthese werkt terug en vult de lege plekken om een ​​algoritme te construeren dat aan die specificaties voldoet, nieuwe input gegeven. De techniek wordt gebruikt, bijvoorbeeld, voor eenvoudige componenten van software-engineering.

In het werk van de onderzoekers de grammatica is CSG, weergegeven als bomen. Elk laatste knooppunt (zonder vertakkende knooppunten) vertegenwoordigt een primitieve vorm met duidelijk gedefinieerde parameters, en tussenliggende knooppunten vertegenwoordigen de basismanieren waarop de vormen samenkomen en betrekking hebben.

De onderzoekers ontwikkelden een methode waarmee programmasynthese een volledig 3D-mesh kan scannen en, eigenlijk, denk aan elke mogelijke CSG-boom die het zou kunnen creëren als een nieuw kandidaatprogramma.

Nadat het systeem een ​​invoermesh heeft ontvangen, een voorbewerkingsstap detecteert de mogelijke locaties, oriëntaties, en parameters van alle primitieve vormen. Dit proces creëert een enorme puntenwolk over het oppervlak van de driehoeksmaas. Een speciaal "primitieve detectie"-algoritme leidt uit deze punten de afmetingen af ​​voor elke primitieve vorm waaruit de mesh bestaat.

De onderzoekers bemonsteren vervolgens tonnen punten in de hele 3D-ruimte en markeren ze als binnen of buiten het gaas. Dit helpt bepalen hoe de vormen samenkomen of zich tot elkaar verhouden. Een eenvoudig voorbeeld is een mesh bestaande uit twee bollen, A en B, samengesmolten. Als een bemonsterd punt binnen bol A valt, één binnen bol B, en één op het snijpunt van de twee (binnen zowel A als B), het is hoogstwaarschijnlijk een unie van de twee vormen.

Gezien deze informatie, samen met de primitieve dimensies, programmasynthese zou mogelijk een CGS-boom kunnen creëren. Maar, 3-D meshes van zelfs lage complexiteit zouden programmasynthese vereisen om tienduizenden punten te bemonsteren. Dit zou een enorme zoekruimte creëren die rekenkundig onpraktisch is om te hanteren. "Als alle samples rechtstreeks worden ingevoerd, zal de programmasynthesizer stikken, ' zegt Du.

Om ervoor te zorgen dat het systeem efficiënt werkte, de onderzoekers ontwierpen een bemonsteringsmethode die verschillende kleine subsets van puntmonsters in de 3D-ruimte creëert, wat veel gemakkelijker is voor programmasynthese om te berekenen. Door deze subsets te bemonsteren, het creëert een nieuw kandidaat-programma, " of CGS-boom, dat kan als juist worden beschouwd. Na talloze iteraties - en met behulp van technieken om bepaalde punten en bomen te elimineren - landt het systeem op de juiste CGS-boom voor elke vorm, met de juiste tussenstappen en eindparameters. Alle bewerkte vormen worden teruggevoerd naar de mesh terwijl het systeem de tussenliggende stappen rekenkundig volgt terug naar het uiteindelijke object.

Momenteel, het systeem kan slechts vier primitieve vormen aan:bollen, cilinders, balkjes, en tori (donutvormen). Volgende, de onderzoekers streven ernaar om de complexiteit van de CSG-grammatica te vergroten om meer vormen en meer modifiers buiten alleen Booleaanse operatoren aan te kunnen.

Dit verhaal is opnieuw gepubliceerd met dank aan MIT News (web.mit.edu/newsoffice/), een populaire site met nieuws over MIT-onderzoek, innovatie en onderwijs.