Merge commit 'origin/gallium-0.1' into gallium-0.2
[mesa.git] / src / mesa / vbo / vbo_split_copy.c
1
2 /*
3 * Mesa 3-D graphics library
4 * Version: 6.5
5 *
6 * Copyright (C) 1999-2006 Brian Paul All Rights Reserved.
7 *
8 * Permission is hereby granted, free of charge, to any person obtaining a
9 * copy of this software and associated documentation files (the "Software"),
10 * to deal in the Software without restriction, including without limitation
11 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
12 * and/or sell copies of the Software, and to permit persons to whom the
13 * Software is furnished to do so, subject to the following conditions:
14 *
15 * The above copyright notice and this permission notice shall be included
16 * in all copies or substantial portions of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
21 * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
22 * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
23 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 *
25 * Authors:
26 * Keith Whitwell <keith@tungstengraphics.com>
27 */
28
29 /* Split indexed primitives with per-vertex copying.
30 */
31
32 #include "main/glheader.h"
33 #include "main/imports.h"
34 #include "main/macros.h"
35 #include "main/enums.h"
36 #include "main/mtypes.h"
37
38 #include "vbo_split.h"
39 #include "vbo.h"
40
41
42 #define ELT_TABLE_SIZE 16
43
44 /* Used for vertex-level splitting of indexed buffers. Note that
45 * non-indexed primitives may be converted to indexed in some cases
46 * (eg loops, fans) in order to use this splitting path.
47 */
48 struct copy_context {
49
50 GLcontext *ctx;
51 const struct gl_client_array **array;
52 const struct _mesa_prim *prim;
53 GLuint nr_prims;
54 const struct _mesa_index_buffer *ib;
55 vbo_draw_func draw;
56
57 const struct split_limits *limits;
58
59 struct {
60 GLuint attr;
61 GLuint size;
62 const struct gl_client_array *array;
63 const GLubyte *src_ptr;
64
65 struct gl_client_array dstarray;
66
67 } varying[VERT_ATTRIB_MAX];
68 GLuint nr_varying;
69
70 const struct gl_client_array *dstarray_ptr[VERT_ATTRIB_MAX];
71 struct _mesa_index_buffer dstib;
72
73 GLuint *translated_elt_buf;
74 const GLuint *srcelt;
75
76 /* A baby hash table to avoid re-emitting (some) duplicate
77 * vertices when splitting indexed primitives.
78 */
79 struct {
80 GLuint in;
81 GLuint out;
82 } vert_cache[ELT_TABLE_SIZE];
83
84
85 GLuint vertex_size;
86 GLubyte *dstbuf;
87 GLubyte *dstptr; /* dstptr == dstbuf + dstelt_max * vertsize */
88 GLuint dstbuf_size; /* in vertices */
89 GLuint dstbuf_nr; /* count of emitted vertices, also the
90 * largest value in dstelt. Our
91 * MaxIndex.
92 */
93
94 GLuint *dstelt;
95 GLuint dstelt_nr;
96 GLuint dstelt_size;
97
98 #define MAX_PRIM 32
99 struct _mesa_prim dstprim[MAX_PRIM];
100 GLuint dstprim_nr;
101
102 };
103
104
105 static GLuint type_size( GLenum type )
106 {
107 switch(type) {
108 case GL_BYTE: return sizeof(GLbyte);
109 case GL_UNSIGNED_BYTE: return sizeof(GLubyte);
110 case GL_SHORT: return sizeof(GLshort);
111 case GL_UNSIGNED_SHORT: return sizeof(GLushort);
112 case GL_INT: return sizeof(GLint);
113 case GL_UNSIGNED_INT: return sizeof(GLuint);
114 case GL_FLOAT: return sizeof(GLfloat);
115 case GL_DOUBLE: return sizeof(GLdouble);
116 default: return 0;
117 }
118 }
119
120 static GLuint attr_size( const struct gl_client_array *array )
121 {
122 return array->Size * type_size(array->Type);
123 }
124
125
126 /* Starts returning true slightly before the buffer fills, to ensure
127 * that there is sufficient room for any remaining vertices to finish
128 * off the prim:
129 */
130 static GLboolean check_flush( struct copy_context *copy )
131 {
132 GLenum mode = copy->dstprim[copy->dstprim_nr].mode;
133
134 if (GL_TRIANGLE_STRIP == mode &&
135 copy->dstelt_nr & 1) { /* see bug9962 */
136 return GL_FALSE;
137 }
138
139 if (copy->dstbuf_nr + 4 > copy->dstbuf_size)
140 return GL_TRUE;
141
142 if (copy->dstelt_nr + 4 > copy->dstelt_size)
143 return GL_TRUE;
144
145 return GL_FALSE;
146 }
147
148 static void flush( struct copy_context *copy )
149 {
150 GLuint i;
151
152 /* Set some counters:
153 */
154 copy->dstib.count = copy->dstelt_nr;
155
156 copy->draw( copy->ctx,
157 copy->dstarray_ptr,
158 copy->dstprim,
159 copy->dstprim_nr,
160 &copy->dstib,
161 0,
162 copy->dstbuf_nr );
163
164 /* Reset all pointers:
165 */
166 copy->dstprim_nr = 0;
167 copy->dstelt_nr = 0;
168 copy->dstbuf_nr = 0;
169 copy->dstptr = copy->dstbuf;
170
171 /* Clear the vertex cache:
172 */
173 for (i = 0; i < ELT_TABLE_SIZE; i++)
174 copy->vert_cache[i].in = ~0;
175 }
176
177
178
179 static void begin( struct copy_context *copy, GLenum mode, GLboolean begin_flag )
180 {
181 struct _mesa_prim *prim = &copy->dstprim[copy->dstprim_nr];
182
183 /* _mesa_printf("begin %s (%d)\n", _mesa_lookup_enum_by_nr(mode), begin_flag); */
184
185 prim->mode = mode;
186 prim->begin = begin_flag;
187 }
188
189
190 /* Use a hashtable to attempt to identify recently-emitted vertices
191 * and avoid re-emitting them.
192 */
193 static GLuint elt(struct copy_context *copy, GLuint elt_idx)
194 {
195 GLuint elt = copy->srcelt[elt_idx];
196 GLuint slot = elt & (ELT_TABLE_SIZE-1);
197
198 /* _mesa_printf("elt %d\n", elt); */
199
200 /* Look up the incoming element in the vertex cache. Re-emit if
201 * necessary.
202 */
203 if (copy->vert_cache[slot].in != elt) {
204 GLubyte *csr = copy->dstptr;
205 GLuint i;
206
207 /* _mesa_printf(" --> emit to dstelt %d\n", copy->dstbuf_nr); */
208
209 for (i = 0; i < copy->nr_varying; i++) {
210 const struct gl_client_array *srcarray = copy->varying[i].array;
211 const GLubyte *srcptr = copy->varying[i].src_ptr + elt * srcarray->StrideB;
212
213 memcpy(csr, srcptr, copy->varying[i].size);
214 csr += copy->varying[i].size;
215
216 if (0)
217 {
218 const GLuint *f = (const GLuint *)srcptr;
219 GLuint j;
220 _mesa_printf(" varying %d: ", i);
221 for(j = 0; j < copy->varying[i].size / 4; j++)
222 _mesa_printf("%x ", f[j]);
223 _mesa_printf("\n");
224 }
225
226 }
227
228 copy->vert_cache[slot].in = elt;
229 copy->vert_cache[slot].out = copy->dstbuf_nr++;
230 copy->dstptr += copy->vertex_size;
231
232 assert(csr == copy->dstptr);
233 assert(copy->dstptr == (copy->dstbuf +
234 copy->dstbuf_nr *
235 copy->vertex_size));
236 }
237 /* else */
238 /* _mesa_printf(" --> reuse vertex\n"); */
239
240 /* _mesa_printf(" --> emit %d\n", copy->vert_cache[slot].out); */
241 copy->dstelt[copy->dstelt_nr++] = copy->vert_cache[slot].out;
242 return check_flush(copy);
243 }
244
245 static void end( struct copy_context *copy, GLboolean end_flag )
246 {
247 struct _mesa_prim *prim = &copy->dstprim[copy->dstprim_nr];
248
249 /* _mesa_printf("end (%d)\n", end_flag); */
250
251 prim->end = end_flag;
252 prim->count = copy->dstelt_nr - prim->start;
253
254 if (++copy->dstprim_nr == MAX_PRIM ||
255 check_flush(copy))
256 flush(copy);
257 }
258
259
260
261 static void replay_elts( struct copy_context *copy )
262 {
263 GLuint i, j, k;
264 GLboolean split;
265
266 for (i = 0; i < copy->nr_prims; i++) {
267 const struct _mesa_prim *prim = &copy->prim[i];
268 const GLuint start = prim->start;
269 GLuint first, incr;
270
271 switch (prim->mode) {
272
273 case GL_LINE_LOOP:
274 /* Convert to linestrip and emit the final vertex explicitly,
275 * but only in the resultant strip that requires it.
276 */
277 j = 0;
278 while (j != prim->count) {
279 begin(copy, GL_LINE_STRIP, prim->begin && j == 0);
280
281 for (split = GL_FALSE; j != prim->count && !split; j++)
282 split = elt(copy, start + j);
283
284 if (j == prim->count) {
285 /* Done, emit final line. Split doesn't matter as
286 * it is always raised a bit early so we can emit
287 * the last verts if necessary!
288 */
289 if (prim->end)
290 (void)elt(copy, start + 0);
291
292 end(copy, prim->end);
293 }
294 else {
295 /* Wrap
296 */
297 assert(split);
298 end(copy, 0);
299 j--;
300 }
301 }
302 break;
303
304 case GL_TRIANGLE_FAN:
305 case GL_POLYGON:
306 j = 2;
307 while (j != prim->count) {
308 begin(copy, prim->mode, prim->begin && j == 0);
309
310 split = elt(copy, start+0);
311 assert(!split);
312
313 split = elt(copy, start+j-1);
314 assert(!split);
315
316 for (; j != prim->count && !split; j++)
317 split = elt(copy, start+j);
318
319 end(copy, prim->end && j == prim->count);
320
321 if (j != prim->count) {
322 /* Wrapped the primitive, need to repeat some vertices:
323 */
324 j -= 1;
325 }
326 }
327 break;
328
329 default:
330 (void)split_prim_inplace(prim->mode, &first, &incr);
331
332 j = 0;
333 while (j != prim->count) {
334
335 begin(copy, prim->mode, prim->begin && j == 0);
336
337 split = 0;
338 for (k = 0; k < first; k++, j++)
339 split |= elt(copy, start+j);
340
341 assert(!split);
342
343 for (; j != prim->count && !split; )
344 for (k = 0; k < incr; k++, j++)
345 split |= elt(copy, start+j);
346
347 end(copy, prim->end && j == prim->count);
348
349 if (j != prim->count) {
350 /* Wrapped the primitive, need to repeat some vertices:
351 */
352 assert(j > first - incr);
353 j -= (first - incr);
354 }
355 }
356 break;
357 }
358 }
359
360 if (copy->dstprim_nr)
361 flush(copy);
362 }
363
364
365 static void replay_init( struct copy_context *copy )
366 {
367 GLcontext *ctx = copy->ctx;
368 GLuint i;
369 GLuint offset;
370 const GLvoid *srcptr;
371
372 /* Make a list of varying attributes and their vbo's. Also
373 * calculate vertex size.
374 */
375 copy->vertex_size = 0;
376 for (i = 0; i < VERT_ATTRIB_MAX; i++) {
377 struct gl_buffer_object *vbo = copy->array[i]->BufferObj;
378
379 if (copy->array[i]->StrideB == 0) {
380 copy->dstarray_ptr[i] = copy->array[i];
381 }
382 else {
383 GLuint j = copy->nr_varying++;
384
385 copy->varying[j].attr = i;
386 copy->varying[j].array = copy->array[i];
387 copy->varying[j].size = attr_size(copy->array[i]);
388 copy->vertex_size += attr_size(copy->array[i]);
389
390 if (vbo->Name && !vbo->Pointer)
391 ctx->Driver.MapBuffer(ctx,
392 GL_ARRAY_BUFFER_ARB,
393 GL_WRITE_ONLY, /* XXX */
394 vbo);
395
396 copy->varying[j].src_ptr = ADD_POINTERS(vbo->Pointer,
397 copy->array[i]->Ptr);
398
399 copy->dstarray_ptr[i] = &copy->varying[j].dstarray;
400 }
401 }
402
403 /* There must always be an index buffer. Currently require the
404 * caller convert non-indexed prims to indexed. Could alternately
405 * do it internally.
406 */
407 if (copy->ib->obj->Name && !copy->ib->obj->Pointer)
408 ctx->Driver.MapBuffer(ctx,
409 GL_ARRAY_BUFFER_ARB, /* XXX */
410 GL_WRITE_ONLY, /* XXX */
411 copy->ib->obj);
412
413 srcptr = (const GLubyte *)ADD_POINTERS(copy->ib->obj->Pointer, copy->ib->ptr);
414
415 switch (copy->ib->type) {
416 case GL_UNSIGNED_BYTE:
417 copy->translated_elt_buf = _mesa_malloc(sizeof(GLuint) * copy->ib->count);
418 copy->srcelt = copy->translated_elt_buf;
419
420 for (i = 0; i < copy->ib->count; i++)
421 copy->translated_elt_buf[i] = ((const GLubyte *)srcptr)[i];
422 break;
423
424 case GL_UNSIGNED_SHORT:
425 copy->translated_elt_buf = _mesa_malloc(sizeof(GLuint) * copy->ib->count);
426 copy->srcelt = copy->translated_elt_buf;
427
428 for (i = 0; i < copy->ib->count; i++)
429 copy->translated_elt_buf[i] = ((const GLushort *)srcptr)[i];
430 break;
431
432 case GL_UNSIGNED_INT:
433 copy->translated_elt_buf = NULL;
434 copy->srcelt = (const GLuint *)srcptr;
435 break;
436 }
437
438
439 /* Figure out the maximum allowed vertex buffer size:
440 */
441 if (copy->vertex_size * copy->limits->max_verts <= copy->limits->max_vb_size) {
442 copy->dstbuf_size = copy->limits->max_verts;
443 }
444 else {
445 copy->dstbuf_size = copy->limits->max_vb_size / copy->vertex_size;
446 }
447
448 /* Allocate an output vertex buffer:
449 *
450 * XXX: This should be a VBO!
451 */
452 copy->dstbuf = _mesa_malloc(copy->dstbuf_size *
453 copy->vertex_size);
454 copy->dstptr = copy->dstbuf;
455
456 /* Setup new vertex arrays to point into the output buffer:
457 */
458 for (offset = 0, i = 0; i < copy->nr_varying; i++) {
459 const struct gl_client_array *src = copy->varying[i].array;
460 struct gl_client_array *dst = &copy->varying[i].dstarray;
461
462 dst->Size = src->Size;
463 dst->Type = src->Type;
464 dst->Stride = copy->vertex_size;
465 dst->StrideB = copy->vertex_size;
466 dst->Ptr = copy->dstbuf + offset;
467 dst->Enabled = GL_TRUE;
468 dst->Normalized = src->Normalized;
469 dst->BufferObj = ctx->Array.NullBufferObj;
470 dst->_MaxElement = copy->dstbuf_size; /* may be less! */
471
472 offset += copy->varying[i].size;
473 }
474
475 /* Allocate an output element list:
476 */
477 copy->dstelt_size = MIN2(65536,
478 copy->ib->count * 2 + 3);
479 copy->dstelt_size = MIN2(copy->dstelt_size,
480 copy->limits->max_indices);
481 copy->dstelt = _mesa_malloc(sizeof(GLuint) * copy->dstelt_size);
482 copy->dstelt_nr = 0;
483
484 /* Setup the new index buffer to point to the allocated element
485 * list:
486 */
487 copy->dstib.count = 0; /* duplicates dstelt_nr */
488 copy->dstib.type = GL_UNSIGNED_INT;
489 copy->dstib.obj = ctx->Array.NullBufferObj;
490 copy->dstib.ptr = copy->dstelt;
491 }
492
493
494 static void replay_finish( struct copy_context *copy )
495 {
496 GLcontext *ctx = copy->ctx;
497 GLuint i;
498
499 /* Free our vertex and index buffers:
500 */
501 _mesa_free(copy->translated_elt_buf);
502 _mesa_free(copy->dstbuf);
503 _mesa_free(copy->dstelt);
504
505 /* Unmap VBO's
506 */
507 for (i = 0; i < copy->nr_varying; i++) {
508 struct gl_buffer_object *vbo = copy->varying[i].array->BufferObj;
509
510 if (vbo->Name && vbo->Pointer)
511 ctx->Driver.UnmapBuffer(ctx, GL_ARRAY_BUFFER_ARB, vbo);
512 }
513
514 /* Unmap index buffer:
515 */
516 if (copy->ib->obj->Name && copy->ib->obj->Pointer) {
517 ctx->Driver.UnmapBuffer(ctx,
518 GL_ARRAY_BUFFER_ARB, /* XXX */
519 copy->ib->obj);
520 }
521 }
522
523 void vbo_split_copy( GLcontext *ctx,
524 const struct gl_client_array *arrays[],
525 const struct _mesa_prim *prim,
526 GLuint nr_prims,
527 const struct _mesa_index_buffer *ib,
528 vbo_draw_func draw,
529 const struct split_limits *limits )
530 {
531 struct copy_context copy;
532 GLuint i;
533
534 memset(&copy, 0, sizeof(copy));
535
536 /* Require indexed primitives:
537 */
538 assert(ib);
539
540 copy.ctx = ctx;
541 copy.array = arrays;
542 copy.prim = prim;
543 copy.nr_prims = nr_prims;
544 copy.ib = ib;
545 copy.draw = draw;
546 copy.limits = limits;
547
548
549 /* Clear the vertex cache:
550 */
551 for (i = 0; i < ELT_TABLE_SIZE; i++)
552 copy.vert_cache[i].in = ~0;
553
554
555 replay_init(&copy);
556 replay_elts(&copy);
557 replay_finish(&copy);
558 }