[an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] (none) [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] (none) [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive]
 
[an error occurred while processing this directive] [an error occurred while processing this directive]
Skåne Sjælland Linux User Group - http://www.sslug.dk Home   Subscribe   Mail Archive   Forum   Calendar   Search
MhonArc Date: [Date Prev] [Date Index] [Date Next]   Thread: [Date Prev] [Thread Index] [Date Next]   MhonArc
 

Re: [PROGRAMMERING] marching cube på 3D net af blandede kantlængder



On Fri, 22 Oct 2004 11:58:35 +0200, Anders Hellerup Madsen wrote:

> Marc Cromme wrote:
>> marching cube går ud fra at alle kubus'er har samme størrelse.
>> Men jeg ønsker at operere på et 3D kubisk net, hvor kuberne har
>> forskellige størrelser, med kantlængder der er en faktor 2^n af hinanden.
>> 
 ....
> 
> Jeg tror aldrig jeg har hørt om nogen metode til at gøre det du vil, på 
> en fornuftig måde, og jeg tror ærligt talt heller ikke man rigtigt kan.
> 
sure - alt er muligt - noget måske lidt bøvlet, som det her, men der
findes udfordringer som er svære at modstå.

> Den problematiske side fra den store kubus har to grænsepunkter, og den 
> skal grænse op imod to sider, der bliver genereret ud fra tre 
> grænsepunkter, hvoraf de to yderpunkter er de samme som den store sides 
> grænsepunkter. For at undgå cracks skal man altså sikre at de tredie 
> grænsepunkt ligger præcis på det punkt hvor siden fra den store kubus 
> bryder kanten mellem de to små kuber.
> 

Netop! Det er udfordringen! Med andre ord skal algoritmen vælge en
subdivision på den dobbelt så lang kant fra en nabo-terning, hvis en
lille terning støder op til en stor terning. 

Men hvad hvis to små terninger's kanter er sammenfaldene med den samme
store nabo ternings kant (i.e. er i forlængelse af hinanden), og hver af
de tre kanter har en divergerende opfattelse om hvor subdivisionen skal
laves ?? Den er tricky!

> Den eneste måde jeg kan se det kan lade sig gøre, er at subdividere det 
> tredie punkt voldsomt meget og så har du jo ikke rigtigt sparet noget.
> 

Øhh? Ikke forstå??

> Jeg er ikke verdensmester i den her slags (hverken programmeringen eller 
> matematikken) men jeg tror, at hvis du vil optimere på algoritmen så 
> skal du i stedet kigge på at cache brydningspunkterne.
> 

Klart - det er første step i optimeringen. Der er ingen grund til at
beregne dem igen og igen, når samme kant findes i 4 tilstødende kubus'er.

> Hvis alle kuberne er lige store, så vil hver side blive delt mellem fire 
> kuber. Det betyder også at den bliver undersøgt for brydninger 
> (intersections) fire gange. Hvis du finder en måde at cache 
> brydningerne, så vil du kunne spare ca. 75% af alle subdivisioner. Det 
> tror jeg giver et bedre resultat.

Det er som sagt en start - meeen det må kunne gøres bedre.

Typisk ønsker man at modelere en isoflade - og dennes komplexitet
skalerer som n^2, hvor n er antallet af kantlængder i selve det totale
volumen man bruger. Men idet volumen komplexiteten skalerer n^3 
(det er ikke sjovt! faktisk ret så dræbende for fine subdivisioner)
spilder man en faktor n for at opnå en given finhedsgrad i overfladen.

Brugen man en hierarkisk volumen model, som kun bruger fine subdivisioner
i nærheden af overfladen, og grove langt væk, er jeg overbevist om at
man i det mindste kan opnå

n^2 * log n  - det er en voldsom besparelse!

Ydermere kan man forstille sig at mange isoflader krummer lidt mange
steder, og krummer kun meget få steder. Ergo er der ingen behov for at
modellere hele overfladen med mange fine trekanter. 

Mit gæt er at man også der kan spare en del, måske op til 

n * log n * log n

i rigtig gode tilfælde.

Bemærk at det er mindre end n^2 !!

Så derfor er det slet ikke sådan en tosset ide at bekymre sig om
marching cubes kan ændres således at den kan arbejde med forskellige
kantlængder. 

Det er sådan set rationalet bag mit spørgsmål.

Men du har ret - jeg har hellere ikke kunne finde noget på nettet derom.

Hilsen, Marc


 
Home   Subscribe   Mail Archive   Index   Calendar   Search

 
 
Questions about the web-pages to <www_admin>. Last modified 2005-08-10, 22:44 CEST [an error occurred while processing this directive]
This page is maintained by [an error occurred while processing this directive]MHonArc [an error occurred while processing this directive] # [an error occurred while processing this directive] *