Erreur de segmentation et fonction récursive.

**azmodai** · 16/12/2009, 15h29

Bonjour,

Afin de décire un arbre entier j'ai construit une fonction récursive. Mais seulement la partie extrême gauche se génère et lorsque les parties droites se lancent j'obtient un jolie segmentation fault .....

Voici la fonction en question :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
 
/* algo de construction des boxes */
void DrawBoxes(bvh *father_bvh, box *father_box) {
 
	#ifdef DEBUG
	printf("-- MARK --");
	#endif
 
	int i,j,k;	
 
	bvh leftchild_bvh;
	box leftchild_box;
 
	bvh rightchild_bvh;
	box rightchild_box;
 
	leftchild_bvh.isALeaf = 0;
	rightchild_bvh.isALeaf = 0;
 
	father_bvh->leftTree = &leftchild_bvh;
	father_bvh->rightTree = &rightchild_bvh;
 
	/* axe a = 0 -> axe x, a = 1 -> axe y, a = 2 -> axe z */
	static int a = 0;
 
	float ga;
	float mediane_a[3];
 
	int left_nbtriangle;
	int right_nbtraingle;
 
	/* 0 : on recupere les valeurs min et max */
 
	float minx = points[father_bvh->indixTriangle[0]];
        float maxx = points[father_bvh->indixTriangle[0]];
        float miny = points[father_bvh->indixTriangle[0] + 1];
        float maxy = points[father_bvh->indixTriangle[0] + 1];
        float minz = points[father_bvh->indixTriangle[0] + 2];
        float maxz = points[father_bvh->indixTriangle[0] + 2];
 
        for(i=0 ; i < father_bvh->nbTriangle ; i++) {
 
                /* X Values */
                if(minx > points[father_bvh->indixTriangle[i]])
                        minx = points[father_bvh->indixTriangle[i]];
                if(maxx < points[father_bvh->indixTriangle[i]])
                        maxx = points[father_bvh->indixTriangle[i]];
 
		/* Y Values */
                if(miny > points[father_bvh->indixTriangle[i] + 1])
                        miny = points[father_bvh->indixTriangle[i] + 1];
                if(maxy < points[father_bvh->indixTriangle[i] + 1])
                        maxy = points[father_bvh->indixTriangle[i] + 1];
 
                /* Z Values */
                if(minz > points[father_bvh->indixTriangle[i] + 2])
                        minz = points[father_bvh->indixTriangle[i] + 2];
                if(maxz < points[father_bvh->indixTriangle[i] + 2])
                        maxz = points[father_bvh->indixTriangle[i] + 2];
        }
 
	/* 1 : on remplit la structure box */
	father_box->xMin = minx;
	father_box->xMax = maxx;	
	father_box->yMin = miny;
	father_box->yMax = maxy;
	father_box->zMin = minz;
	father_box->zMax = maxz;
 
	SaveBVHInfos(*father_bvh, *father_box);
 
	/* 2 : calcul des longeurs en x, en y, en z */
 
	float x = maxx - minx;
	float y = maxy - miny;
	float z = maxz - minz;	 
 
	/* 3 : calcul des medianes */
 
	mediane_a[0] = (x / 2) + minx;
	mediane_a[1] = (y / 2) + miny;
	mediane_a[2] = (z / 2) + minz;
 
	/* 4 : on initialise la memoire */
 
	leftchild_bvh.indixTriangle = (int *)malloc(sizeof(int));
	rightchild_bvh.indixTriangle = (int *)malloc(sizeof(int));
 
	leftchild_bvh.nbTriangle = 0;
	rightchild_bvh.nbTriangle = 0;
 
	/* 5 : on fabrique les boxes et on decompte les triangles */
 
	for(i=0, j=0, k=0 ; i < father_bvh->nbTriangle ; i++) {
 
 
		// t'es sur que c'est bon -> ???		
		// doit faire un saut pour choper les x, y et z ... 
 
		ga = (points[father_bvh->indixTriangle[i]+a] +
		points[father_bvh->indixTriangle[i+1]+a] +
 		points[father_bvh->indixTriangle[i+2]+a]) / 3;
 
		if(ga < mediane_a[a]) {
			leftchild_bvh.indixTriangle = (int  *)realloc(leftchild_bvh.indixTriangle, (sizeof(int)*(j+1+1)));						
			leftchild_bvh.nbTriangle++;
 
			leftchild_bvh.indixTriangle[j] = father_bvh->indixTriangle[i];
			j++;
		} 	
		else {
			rightchild_bvh.indixTriangle = (int *)realloc(rightchild_bvh.indixTriangle, (sizeof(int)*(k+1+1)));
			rightchild_bvh.nbTriangle++;
 
			rightchild_bvh.indixTriangle[k] = father_bvh->indixTriangle[i];
			k++;	
		}
	}
 
	/* 6 : reste */
 
	if(leftchild_bvh.nbTriangle <= BOX_MIN_TRIANGLE_NBR)
		leftchild_bvh.isALeaf = 1;	
 
	if(rightchild_bvh.nbTriangle <= BOX_MIN_TRIANGLE_NBR)
		rightchild_bvh.isALeaf = 1;
 
	leftchild_bvh.depth = father_bvh->depth + 1;
	rightchild_bvh.depth = father_bvh->depth + 1;
 
	/* rotation d'axe */
	a++;
	a = a % 3;
 
	/* fils gauche */
 
	if((!leftchild_bvh.isALeaf) && (leftchild_bvh.depth <= BVH_MAX_TREE_DEPTH)) {
 
		#ifdef DEBUG
		printf("\n<<<<<<<< LEFT CHILD <<<<<<<<<< (leaf:%d)\n",leftchild_bvh.isALeaf);
	        printf("\nLEFT\n");
	        printf("Is a Leaf : %d\n",leftchild_bvh.isALeaf);
	        printf("Depth : %d\n",leftchild_bvh.depth);
	        printf("Nomber of triangle : %d\n",leftchild_bvh.nbTriangle);
	        //for(i = 0 ; i < j ; i++)
	        //      printf("%d\n",leftchild_bvh.indixTriangle[i]);
		#endif
 
		DrawBoxes(&leftchild_bvh, &leftchild_box);
	}
 
 
	if((!rightchild_bvh.isALeaf) && (rightchild_bvh.depth <= BVH_MAX_TREE_DEPTH)) 	{
 
		#ifdef DEBUG
		printf("\n<<<<<<<< RIGHT CHILD <<<<<<<<< (leaf:%d)\n",rightchild_bvh.isALeaf);
 
		printf("\nRIGHT\n");
        	printf("Is a Leaf : %d\n",rightchild_bvh.isALeaf);
       		printf("Depth : %d\n",rightchild_bvh.depth);
        	printf("Number of triangle : %d\n",rightchild_bvh.nbTriangle);
       		//for(i = 0 ; i < k ; i++)
        	//      printf("%d\n",rightchild_bvh.indixTriangle[i]);
		#endif	
 
		DrawBoxes(&rightchild_bvh, &rightchild_box);
	}
}

voilà ce que j'obient en output :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
-- MARK --
<<<<<<<< LEFT CHILD <<<<<<<<<< (leaf:0)
 
LEFT
Is a Leaf : 0
Depth : 2
Nomber of triangle : 656
-- MARK --
<<<<<<<< LEFT CHILD <<<<<<<<<< (leaf:0)
 
LEFT
Is a Leaf : 0
Depth : 3
Nomber of triangle : 392
-- MARK --
<<<<<<<< LEFT CHILD <<<<<<<<<< (leaf:0)
 
LEFT
Is a Leaf : 0
Depth : 4
Nomber of triangle : 387
-- MARK --
<<<<<<<< RIGHT CHILD <<<<<<<<< (leaf:0)
 
RIGHT
Is a Leaf : 0
Depth : 5
Number of triangle : 386
Segmentation fault

À noter que dans le dernier cas elle ne rentre même pas dans la fonction !
(pas de --MARK--).

Je comprends pas ce qu'il ce passe.
Comment pense-vous que je puisse régler ce problème ?

merci,

**diogene** · 16/12/2009, 15h40

À noter que dans le dernier cas elle ne rentre même pas dans la fonction !
(pas de --MARK--).

Pas certain : la fonction peut avorter avant la sortie du message. Forcer l'affichage immédiat en terminant --MARK-- par un '\n' (ou utiliser stderr)

**azmodai** · 16/12/2009, 16h25

Merci diogene,
Grâce à ça j'ai pu localiser le problème.

le segmentation fault se déclare ici :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
		ga = (points[father_bvh->indixTriangle[i]+a] +
		points[father_bvh->indixTriangle[i+1]+a] +
 		points[father_bvh->indixTriangle[i+2]+a]) / 3;

points est un tableau de 804*3 éléments et indixTriangle[i+2]+a = 123746 !
avec i = 384 et a = 1 ; ce qui donne indixTriangle[384+2]+1 = 2401 lorsque je lis le tableau indixTriangle ; déjà il y a un gros problème de nombre
je ne comprend pas comment indixTriangle[i+2]+a = 123746 alors qu'il est égal à 2401....
j'ai beau relancer le binaire je tombe toujours sur 123746 ce qui exclut un problème de mémoire ...

auriez-vous une explication sur ce drôle de phénoméne ?

merci,

j'ai beau relancer le binaire j'obtient 123746,

**diogene** · 16/12/2009, 18h17

Quelle est la profondeur de récursivité lorsque ce phénomène se produit ?
Si elle est trop grande, tu risques l'explosion de la pile.

points est une variable globale ? Déclarée comment ?

**olibara** · 16/12/2009, 20h34

Moi je n'aime pas la récursivité !
C'est un truc académique
Mais tres gourmand en ressource
Et compliqué a tracer

Chaque fois que je peux, je l'evite
C'est toujours plus performant et plus facile a debuguer !!

N.B. C'est du Delaunay ou du Voronoi que tu fais ?

**azmodai** · 16/12/2009, 20h37

Dans l'exemple précédent ça ne va pas plus loin qu'une profondeur de 5.
Mais mon programme est configuré pour que cela n'aille pas plus loin que 10

points est une var globale, c'est un tableau de float, de 804*9 élements

tu penses que je fais exploser la pile ?
je pensais en être très loin ....

**azmodai** · 16/12/2009, 20h40

Envoyé par olibara

Moi je n'aime pas la récursivité !
C'est un truc académique
Mais tres gourmand en ressource
Et compliqué a tracer

Chaque fois que je peux, je l'evite
C'est toujours plus performant et plus facile a debuguer !!

N.B. C'est du Delaunay ou du Voronoi que tu fais ?

Non c'est un BVH pour du ray tracing.
(découpage en boxes de la zone d'impacte pour accélérer les perfs)

Erreur de segmentation et fonction récursive.

C

Discussions similaires

Partager

Partager