1
2/*
3 * Mesa 3-D graphics library
4 *
5 * Copyright (C) 1999-2006  Brian Paul   All Rights Reserved.
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a
8 * copy of this software and associated documentation files (the "Software"),
9 * to deal in the Software without restriction, including without limitation
10 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
11 * and/or sell copies of the Software, and to permit persons to whom the
12 * Software is furnished to do so, subject to the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be included
15 * in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
20 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
21 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
22 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
23 * OTHER DEALINGS IN THE SOFTWARE.
24 *
25 * Authors:
26 *    Keith Whitwell <keithw@vmware.com>
27 */
28
29
30#include "main/mtypes.h"
31#include "main/macros.h"
32#include "main/enums.h"
33#include "main/glformats.h"
34#include "vbo_split.h"
35
36
37#define MAX_PRIM 32
38
39/* Used for splitting without copying. No attempt is made to handle
40 * too large indexed vertex buffers: In general you need to copy to do
41 * that.
42 */
43struct split_context {
44   struct gl_context *ctx;
45   const struct gl_vertex_array **array;
46   const struct _mesa_prim *prim;
47   GLuint nr_prims;
48   const struct _mesa_index_buffer *ib;
49   GLuint min_index;
50   GLuint max_index;
51   vbo_draw_func draw;
52
53   const struct split_limits *limits;
54   GLuint limit;
55
56   struct _mesa_prim dstprim[MAX_PRIM];
57   GLuint dstprim_nr;
58};
59
60
61
62
63static void flush_vertex( struct split_context *split )
64{
65   struct gl_context *ctx = split->ctx;
66   const struct gl_vertex_array **saved_arrays = ctx->Array._DrawArrays;
67   struct _mesa_index_buffer ib;
68   GLuint i;
69
70   if (!split->dstprim_nr)
71      return;
72
73   if (split->ib) {
74      ib = *split->ib;
75
76      ib.count = split->max_index - split->min_index + 1;
77      ib.ptr = (const void *)((const char *)ib.ptr +
78                              split->min_index * _mesa_sizeof_type(ib.type));
79
80      /* Rebase the primitives to save index buffer entries. */
81      for (i = 0; i < split->dstprim_nr; i++)
82	 split->dstprim[i].start -= split->min_index;
83   }
84
85   assert(split->max_index >= split->min_index);
86
87   ctx->Array._DrawArrays = split->array;
88   ctx->NewDriverState |= ctx->DriverFlags.NewArray;
89
90   split->draw(ctx,
91	       split->dstprim,
92	       split->dstprim_nr,
93	       split->ib ? &ib : NULL,
94	       !split->ib,
95	       split->min_index,
96	       split->max_index,
97	       NULL, 0, NULL);
98
99   ctx->Array._DrawArrays = saved_arrays;
100   ctx->NewDriverState |= ctx->DriverFlags.NewArray;
101
102   split->dstprim_nr = 0;
103   split->min_index = ~0;
104   split->max_index = 0;
105}
106
107
108static struct _mesa_prim *next_outprim( struct split_context *split )
109{
110   if (split->dstprim_nr == MAX_PRIM-1) {
111      flush_vertex(split);
112   }
113
114   {
115      struct _mesa_prim *prim = &split->dstprim[split->dstprim_nr++];
116      memset(prim, 0, sizeof(*prim));
117      return prim;
118   }
119}
120
121static void update_index_bounds(struct split_context *split,
122				const struct _mesa_prim *prim)
123{
124   split->min_index = MIN2(split->min_index, prim->start);
125   split->max_index = MAX2(split->max_index, prim->start + prim->count - 1);
126}
127
128/* Return the maximum amount of vertices that can be emitted for a
129 * primitive starting at 'prim->start', depending on the previous
130 * index bounds.
131 */
132static GLuint get_max_vertices(struct split_context *split,
133			       const struct _mesa_prim *prim)
134{
135   if ((prim->start > split->min_index &&
136	prim->start - split->min_index >= split->limit) ||
137       (prim->start < split->max_index &&
138        split->max_index - prim->start >= split->limit))
139      /* "prim" starts too far away from the old range. */
140      return 0;
141
142   return MIN2(split->min_index, prim->start) + split->limit - prim->start;
143}
144
145/* Break large primitives into smaller ones.  If not possible, convert
146 * the primitive to indexed and pass to split_elts().
147 */
148static void split_prims( struct split_context *split)
149{
150   GLuint i;
151
152   for (i = 0; i < split->nr_prims; i++) {
153      const struct _mesa_prim *prim = &split->prim[i];
154      GLuint first, incr;
155      GLboolean split_inplace = split_prim_inplace(prim->mode, &first, &incr);
156      GLuint available = get_max_vertices(split, prim);
157      GLuint count = prim->count - (prim->count - first) % incr;
158
159      if (prim->count < first)
160	 continue;
161
162      if ((available < count && !split_inplace) ||
163	  (available < first && split_inplace)) {
164	 flush_vertex(split);
165	 available = get_max_vertices(split, prim);
166      }
167
168      if (available >= count) {
169	 struct _mesa_prim *outprim = next_outprim(split);
170
171	 *outprim = *prim;
172	 update_index_bounds(split, outprim);
173      }
174      else if (split_inplace) {
175	 GLuint j, nr;
176
177	 for (j = 0 ; j < count ; ) {
178	    GLuint remaining = count - j;
179	    struct _mesa_prim *outprim = next_outprim(split);
180
181	    nr = MIN2( available, remaining );
182	    nr -= (nr - first) % incr;
183
184	    outprim->mode = prim->mode;
185	    outprim->begin = (j == 0 && prim->begin);
186	    outprim->end = (nr == remaining && prim->end);
187	    outprim->start = prim->start + j;
188	    outprim->count = nr;
189            outprim->num_instances = prim->num_instances;
190            outprim->base_instance = prim->base_instance;
191
192	    update_index_bounds(split, outprim);
193
194	    if (nr == remaining) {
195	       /* Finished.
196		*/
197	       j += nr;
198	    }
199	    else {
200	       /* Wrapped the primitive:
201		*/
202	       j += nr - (first - incr);
203	       flush_vertex(split);
204	       available = get_max_vertices(split, prim);
205	    }
206	 }
207      }
208      else if (split->ib == NULL) {
209	 /* XXX: could at least send the first max_verts off from the
210	  * inplace buffers.
211	  */
212
213	 /* else convert to indexed primitive and pass to split_elts,
214	  * which will do the necessary copying and turn it back into a
215	  * vertex primitive for rendering...
216	  */
217	 struct _mesa_index_buffer ib;
218	 struct _mesa_prim tmpprim;
219	 GLuint *elts = malloc(count * sizeof(GLuint));
220	 GLuint j;
221
222	 for (j = 0; j < count; j++)
223	    elts[j] = prim->start + j;
224
225	 ib.count = count;
226	 ib.type = GL_UNSIGNED_INT;
227	 ib.obj = split->ctx->Shared->NullBufferObj;
228	 ib.ptr = elts;
229
230	 tmpprim = *prim;
231	 tmpprim.indexed = 1;
232	 tmpprim.start = 0;
233	 tmpprim.count = count;
234         tmpprim.num_instances = 1;
235         tmpprim.base_instance = 0;
236
237	 flush_vertex(split);
238
239	 vbo_split_copy(split->ctx,
240			split->array,
241			&tmpprim, 1,
242			&ib,
243			split->draw,
244			split->limits);
245
246	 free(elts);
247      }
248      else {
249	 flush_vertex(split);
250
251	 vbo_split_copy(split->ctx,
252			split->array,
253			prim, 1,
254			split->ib,
255			split->draw,
256			split->limits);
257      }
258   }
259
260   flush_vertex(split);
261}
262
263
264void vbo_split_inplace( struct gl_context *ctx,
265			const struct gl_vertex_array *arrays[],
266			const struct _mesa_prim *prim,
267			GLuint nr_prims,
268			const struct _mesa_index_buffer *ib,
269			GLuint min_index,
270			GLuint max_index,
271			vbo_draw_func draw,
272			const struct split_limits *limits )
273{
274   struct split_context split;
275
276   memset(&split, 0, sizeof(split));
277
278   split.ctx = ctx;
279   split.array = arrays;
280   split.prim = prim;
281   split.nr_prims = nr_prims;
282   split.ib = ib;
283
284   /* Empty interval, makes calculations simpler. */
285   split.min_index = ~0;
286   split.max_index = 0;
287
288   split.draw = draw;
289   split.limits = limits;
290   split.limit = ib ? limits->max_indices : limits->max_verts;
291
292   split_prims( &split );
293}
294
295
296