Teksturowanie trójkąta - StackOverflowException

Odpowiedz Nowy wątek
2011-08-29 12:13
Danielak
0

Zadanie które realizuje polega na na łożeniutekstury z jednego trójkąta na drugi trójkąt.
zadanie to realizuje przy pomocy dwóch obiektów Bitmap.
Jednym z nich wykorzystuję do zaznaczenia trójkąta wraz z teksturą a druga do utworzenia trójkąta na którego będę nakładał teksturę z pierwszego.

Całość zadania opieram o współrzędne barycentryczne.

Problem pojawia się gdy trójkąt do teksturowania jest duży, wtedy aplikacja zwraca mi wyjątek
An unhandled exception of type 'System.StackOverflowException' occurred in System.Drawing.dll

Myślę, że jest to związane z wywołaniami rekurencyjnymi ale nie za bardzo mam pomysł w jaki sposób mogę to obejść?

Pozostało 580 znaków

2011-08-29 12:22
0

Nie używać rekurencji.

Pozostało 580 znaków

2011-08-29 12:52
msm
0

@somekind - W wersji x64 jest już tail-call optimization więc można by przerobić rekurencję na ogonową. Ale w C# TCO to optymalizacja raczej niż sposób na projektowania algorytmów (bo nie ma jej w standardzie) więc to raczej zły pomysł.

@Autor - Jeśli chcesz zostawić kod jak jest - zmień rozmiar stosu: http://www.atalasoft.com/cs/b[...]memory-management-part-3.aspx

Albo po prostu zmień kod z rekurencyjnego na iteracyjny...

PS. jeszcze jedno - ciekawą musisz mieć tą rekurencję jeśli wyczerpuje stos.
Zakładając że masz funkcję f która rekurencyjnie wywołuje 2 razy sama siebie i przyjmuje 2 parametry typu int - żeby wyczerpał Ci się stos musiałbyś zagnieździć ją ponad 125000 razy. Tylko że przy takim zagnieżdżeniu łączna ilość wywołań funkcji wyniosłaby 21 + 22 + 23 + 24 + ... + 2124999 + 2125000. Żeby dać Ci wyobrażenie tej liczby, to samo 2 ^ 125000 wynosi http://pastebin.com/CeAb8Eea
Jesteś pewien że musisz tyle razy wywołać tą funkcję (hint: nie.)?

Poszukaj w tym programie nieskończonej rekurencji, to pewnie ona wykańcza stos.

edytowany 3x, ostatnio: msm, 2011-08-29 17:18
Suma tego ciągu wynosi 2^125001 - 2, prosty szereg geometryczny :] - Wibowit 2011-08-29 17:47

Pozostało 580 znaków

2011-08-29 13:24
0

MSM:
Skąd ci taki wynik wyszedł? Wystarczy 125000 wywołań normalnej rekurencyjnej funkcji, aby zapchać stos.

public class Main {
 
    int sum(int from, int to) {
        return from > to ? 0 : from + sum(from + 1, to);
    }
 
    void run() {
        System.out.println(sum(1, 234567));
    }
 
    public static void main(String[] args) {
        new Main().run();
    }
}

SOE od razu :]

Inna sprawa to to, że HotSpot nie robi TCO (przynajmniej domyślnie).


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
Trochę ciężko to było wytłumaczyć, ale starałem się. Chodziło mi o to że jeśli funkcja jest faktycznie rekurencyjna (tzn. wywołuje się co najmniej 2 razy - taki np. quicksort - i zmienienie jej na iterację mogłoby być trudniejsze) to 125000 zagnieżdżeń spowodowałoby w sumie wykonanie dużej ilości kodu (a konkretnie ten właśnie łańcuszek 2<sup>1 + 2</sup>2 ...). - msm 2011-08-29 17:17
Wszystko jasne, miałem literówkę i zamiast 'wywołuje się 2 razymiałem bezsensownewywołuje się z razy` (zrazy? Wieprzowe?) - msm 2011-08-29 17:19
W przypadku prostej implementacji QuickSorta, czyli bez wprost rekurencji ogonowej na większej partycji, może dojść do sytuacji brzegowej, tzn w każdym wywołaniu QuickSorta druga partycja miałaby jeden element, a pierwsza resztę. W takiej sytuacji rozmiar stosu jest liniowy. Jest o tym na Wiki. Motyw jest generalnie taki, że podzadania nie muszą mieć równych wielkości. Jeśli podzadania (tzn te w wywołaniach rekurencyjnych) są o co najmniej stały współczynnik mniejsze od zadania bazowego, wtedy rozmiar stosu jest logarytmiczny. - Wibowit 2011-08-29 17:45

Pozostało 580 znaków

2011-08-29 14:07
0

MSM ma rację. Sprawdź czy nie wywołuje Ci się rekurencja w nieskończoność - ja widziałem ten wyjątek właśnie w takich sytuacjach.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0