lxdream 0.9.1| filename | src/pvr2/rendsort.c |
| changeset | 1154:5225c7c059ce |
| prev | 1143:8ec0f1f990aa |
| next | 1298:d0eb2307b847 |
| author | nkeynes |
| date | Fri Mar 02 23:49:10 2012 +1000 (12 years ago) |
| permissions | -rw-r--r-- |
| last change | Android WIP: * Rename gui_jni.c to gui_android.c - now quite android specific. * Implement generic EGL driver with very minimal Java wrapper * Run emulation in separate thread, and implement simple queue for inter-thread communication. * Add menu/action-bar items for start + reset |
| view | annotate | diff | log | raw |
1 /**
2 * $Id$
3 *
4 * PVR2 renderer routines for depth sorted polygons
5 *
6 * Copyright (c) 2005 Nathan Keynes.
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 */
18 #include <sys/time.h>
19 #include <string.h>
20 #include <assert.h>
21 #include "pvr2/pvr2.h"
22 #include "pvr2/scene.h"
23 #include "asic.h"
25 #define MIN3( a,b,c ) ((a) < (b) ? ( (a) < (c) ? (a) : (c) ) : ((b) < (c) ? (b) : (c)) )
26 #define MAX3( a,b,c ) ((a) > (b) ? ( (a) > (c) ? (a) : (c) ) : ((b) > (c) ? (b) : (c)) )
27 #define EPSILON 0.0001
29 struct sort_triangle {
30 struct polygon_struct *poly;
31 int triangle_num; // triangle number in the poly, from 0
32 /* plane equation */
33 float mx, my, mz, d;
34 float bounds[6]; /* x1,x2,y1,y2,z1,z2 */
35 };
37 #define SENTINEL 0xDEADBEEF
39 /**
40 * Count the number of triangles in the list starting at the given
41 * pvr memory address. This is an upper bound as it includes
42 * triangles that have been culled out.
43 */
44 static int sort_count_triangles( pvraddr_t tile_entry ) {
45 uint32_t *tile_list = (uint32_t *)(pvr2_main_ram+tile_entry);
46 int count = 0;
47 while(1) {
48 uint32_t entry = *tile_list++;
49 if( entry >> 28 == 0x0F ) {
50 break;
51 } else if( entry >> 28 == 0x0E ) {
52 tile_list = (uint32_t *)(pvr2_main_ram+(entry&0x007FFFFF));
53 } else if( entry >> 29 == 0x04 ) { /* Triangle array */
54 count += ((entry >> 25) & 0x0F)+1;
55 } else if( entry >> 29 == 0x05 ) { /* Quad array */
56 count += ((((entry >> 25) & 0x0F)+1)<<1);
57 } else { /* Polygon */
58 struct polygon_struct *poly = pvr2_scene.buf_to_poly_map[entry&0x000FFFFF];
59 while( poly != NULL ) {
60 if( poly->vertex_count != 0 )
61 count += poly->vertex_count-2;
62 poly = poly->sub_next;
63 }
64 }
65 }
66 return count;
67 }
69 static void sort_add_triangle( struct sort_triangle *triangle, struct polygon_struct *poly, int index )
70 {
71 struct vertex_struct *vertexes = &pvr2_scene.vertex_array[poly->vertex_index+index];
72 triangle->poly = poly;
73 triangle->triangle_num = index;
75 /* Compute triangle bounding-box */
76 triangle->bounds[0] = MIN3(vertexes[0].x,vertexes[1].x,vertexes[2].x);
77 triangle->bounds[1] = MAX3(vertexes[0].x,vertexes[1].x,vertexes[2].x);
78 triangle->bounds[2] = MIN3(vertexes[0].y,vertexes[1].y,vertexes[2].y);
79 triangle->bounds[3] = MAX3(vertexes[0].y,vertexes[1].y,vertexes[2].y);
80 triangle->bounds[4] = MIN3(vertexes[0].z,vertexes[1].z,vertexes[2].z);
81 triangle->bounds[5] = MAX3(vertexes[0].z,vertexes[1].z,vertexes[2].z);
83 /* Compute plane equation */
84 float sx = vertexes[1].x - vertexes[0].x;
85 float sy = vertexes[1].y - vertexes[0].y;
86 float sz = vertexes[1].z - vertexes[0].z;
87 float tx = vertexes[2].x - vertexes[0].x;
88 float ty = vertexes[2].y - vertexes[0].y;
89 float tz = vertexes[2].z - vertexes[0].z;
90 triangle->mx = sy*tz - sz*ty;
91 triangle->my = sz*tx - sx*tz;
92 triangle->mz = sx*ty - sy*tx;
93 triangle->d = -vertexes[0].x*triangle->mx -
94 vertexes[0].y*triangle->my -
95 vertexes[0].z*triangle->mz;
96 }
100 /**
101 * Extract a triangle list from the tile (basically indexes into the polygon list, plus
102 * computing maxz while we go through it
103 */
104 int sort_extract_triangles( pvraddr_t tile_entry, struct sort_triangle *triangles )
105 {
106 uint32_t *tile_list = (uint32_t *)(pvr2_main_ram+tile_entry);
107 int strip_count;
108 struct polygon_struct *poly;
109 int count = 0, i;
111 while(1) {
112 uint32_t entry = *tile_list++;
113 switch( entry >> 28 ) {
114 case 0x0F:
115 return count; // End-of-list
116 case 0x0E:
117 tile_list = (uint32_t *)(pvr2_main_ram + (entry&0x007FFFFF));
118 break;
119 case 0x08: case 0x09:
120 strip_count = ((entry >> 25) & 0x0F)+1;
121 poly = pvr2_scene.buf_to_poly_map[entry&0x000FFFFF];
122 while( strip_count > 0 ) {
123 assert( poly != NULL );
124 if( poly->vertex_count != 0 ) {
125 /* Triangle could point to a strip, but we only want
126 * the first one in this case
127 */
128 sort_add_triangle( &triangles[count], poly, 0 );
129 count++;
130 }
131 poly = poly->next;
132 strip_count--;
133 }
134 break;
135 case 0x0A: case 0x0B:
136 strip_count = ((entry >> 25) & 0x0F)+1;
137 poly = pvr2_scene.buf_to_poly_map[entry&0x000FFFFF];
138 while( strip_count > 0 ) {
139 assert( poly != NULL );
140 for( i=0; i+2<poly->vertex_count && i < 2; i++ ) {
141 /* Note: quads can't have sub-polys */
142 sort_add_triangle( &triangles[count], poly, i );
143 count++;
144 }
145 poly = poly->next;
146 strip_count--;
147 }
148 break;
149 default:
150 if( entry & 0x7E000000 ) {
151 poly = pvr2_scene.buf_to_poly_map[entry&0x000FFFFF];
152 /* FIXME: This could end up including a triangle that was
153 * excluded from the tile, if it is part of a strip that
154 * still has some other triangles in the tile.
155 * (This couldn't happen with TA output though).
156 */
157 while( poly != NULL ) {
158 for( i=0; i+2<poly->vertex_count; i++ ) {
159 sort_add_triangle( &triangles[count], poly, i );
160 count++;
161 }
162 poly = poly->sub_next;
163 }
164 }
165 }
166 }
168 }
170 void sort_render_triangles( struct sort_triangle **triangles, int num_triangles )
171 {
172 int i;
173 for( i=0; i<num_triangles; i++ ) {
174 struct polygon_struct *poly = triangles[i]->poly;
175 gl_render_triangle(triangles[i]->poly, triangles[i]->triangle_num);
176 }
177 }
179 static int sort_triangle_compare( const void *a, const void *b )
180 {
181 const struct sort_triangle *tri1 = a;
182 const struct sort_triangle *tri2 = b;
183 if( tri1->bounds[5] <= tri2->bounds[4] )
184 return 1; /* tri1 is entirely under tri2 */
185 else if( tri2->bounds[5] <= tri1->bounds[4] )
186 return -1; /* tri2 is entirely under tri1 */
187 else if( tri1->bounds[1] <= tri2->bounds[0] ||
188 tri2->bounds[1] <= tri1->bounds[0] ||
189 tri1->bounds[3] <= tri2->bounds[2] ||
190 tri2->bounds[3] <= tri1->bounds[2] )
191 return 0; /* tri1 and tri2 don't actually overlap at all */
192 else {
193 struct vertex_struct *tri1v = &pvr2_scene.vertex_array[tri1->poly->vertex_index + tri1->triangle_num];
194 struct vertex_struct *tri2v = &pvr2_scene.vertex_array[tri2->poly->vertex_index + tri2->triangle_num];
195 float v[3];
196 int i;
197 for( i=0; i<3; i++ ) {
198 v[i] = tri1->mx * tri2v[i].x + tri1->my * tri2v[i].y + tri1->mz * tri2v[i].z + tri1->d;
199 if( v[i] > -EPSILON && v[i] < EPSILON ) v[i] = 0;
200 }
201 if( v[0] == 0 && v[1] == 0 && v[2] == 0 ) {
202 return 0; /* coplanar */
203 }
204 if( (v[0] >=0 && v[1] >= 0 && v[2] >= 0) ||
205 (v[0] <= 0 && v[1] <= 0 && v[2] <= 0) ) {
206 /* Tri is on one side of the plane. Pick an arbitrary point to determine which side */
207 float t1z = -(tri1->mx * tri2v[0].x + tri1->my * tri2v[0].y + tri1->d) / tri1->mz;
208 return tri2v[0].z - t1z;
209 }
211 /* If the above test failed, then tri2 intersects tri1's plane. This
212 * doesn't necessarily mean the triangles intersect (although they may).
213 * For now just return 0, and come back to this later as it's a fairly
214 * uncommon case in practice.
215 */
216 return 0;
217 }
218 }
220 /**
221 * This is pretty much a standard merge sort (Unfortunately can't depend on
222 * the system to provide one. Note we can't use quicksort here - the sort
223 * must be stable to preserve the order of coplanar triangles.
224 */
225 static void sort_triangles( struct sort_triangle **triangles, int num_triangles, struct sort_triangle **out )
226 {
227 if( num_triangles > 2 ) {
228 int l = num_triangles>>1, r=num_triangles-l, i=0,j=0;
229 struct sort_triangle *left[l];
230 struct sort_triangle *right[r];
231 sort_triangles( triangles, l, left );
232 sort_triangles( triangles+l, r, right );
234 /* Merge */
235 while(1) {
236 if( sort_triangle_compare(left[i], right[j]) <= 0 ) {
237 *out++ = left[i++];
238 if( i == l ) {
239 memcpy( out, &right[j], (r-j)*sizeof(struct sort_triangle *) );
240 break;
241 }
242 } else {
243 *out++ = right[j++];
244 if( j == r ) {
245 memcpy( out, &left[i], (l-i)*sizeof(struct sort_triangle *) );
246 break;
247 }
248 }
249 }
250 } else if( num_triangles == 2 ) {
251 if( sort_triangle_compare(triangles[0], triangles[1]) <= 0 ) {
252 out[0] = triangles[0];
253 out[1] = triangles[1];
254 } else {
255 struct sort_triangle *tmp = triangles[0];
256 out[0] = triangles[1];
257 out[1] = tmp;
258 }
259 } else {
260 out[0] = triangles[0];
261 }
262 }
264 void render_autosort_tile( pvraddr_t tile_entry, int render_mode )
265 {
266 int num_triangles = sort_count_triangles(tile_entry);
267 if( num_triangles == 0 ) {
268 return; /* nothing to do */
269 } else if( num_triangles == 1 ) { /* Triangle can hardly overlap with itself */
270 glDepthMask(GL_FALSE);
271 glDepthFunc(GL_GEQUAL);
272 gl_render_tilelist(tile_entry, FALSE);
273 } else { /* Ooh boy here we go... */
274 int i;
275 struct sort_triangle triangles[num_triangles+1];
276 struct sort_triangle *triangle_order[num_triangles+1];
277 triangles[num_triangles].poly = (void *)SENTINEL;
278 for( i=0; i<num_triangles; i++ ) {
279 triangle_order[i] = &triangles[i];
280 }
281 int extracted_triangles = sort_extract_triangles(tile_entry, triangles);
282 assert( extracted_triangles <= num_triangles );
283 sort_triangles( triangle_order, extracted_triangles, triangle_order );
284 glDepthMask(GL_FALSE);
285 glDepthFunc(GL_GEQUAL);
286 sort_render_triangles(triangle_order, extracted_triangles);
287 assert( triangles[num_triangles].poly == (void *)SENTINEL );
288 }
289 }
.