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 "vbo/vbo.h"
34
35#include "t_split.h"
36
37
38#define MAX_PRIM 32
39
40/* Used for splitting without copying. No attempt is made to handle
41 * too large indexed vertex buffers: In general you need to copy to do
42 * that.
43 */
44struct split_context {
45   struct gl_context *ctx;
46   const struct tnl_vertex_array *array;
47   const struct _mesa_prim *prim;
48   GLuint nr_prims;
49   const struct _mesa_index_buffer *ib;
50   GLuint min_index;
51   GLuint max_index;
52   tnl_draw_func draw;
53
54   const struct split_limits *limits;
55   GLuint limit;
56
57   struct _mesa_prim dstprim[MAX_PRIM];
58   GLuint dstprim_nr;
59};
60
61
62
63
64static void
65flush_vertex( struct split_context *split)
66{
67   struct gl_context *ctx = split->ctx;
68   struct _mesa_index_buffer ib;
69   GLuint i;
70
71   if (!split->dstprim_nr)
72      return;
73
74   if (split->ib) {
75      ib = *split->ib;
76
77      ib.count = split->max_index - split->min_index + 1;
78      ib.ptr = (const void *)((const char *)ib.ptr +
79                              split->min_index * ib.index_size);
80
81      /* Rebase the primitives to save index buffer entries. */
82      for (i = 0; i < split->dstprim_nr; i++)
83         split->dstprim[i].start -= split->min_index;
84   }
85
86   assert(split->max_index >= split->min_index);
87
88   split->draw(ctx,
89               split->array,
90               split->dstprim,
91               split->dstprim_nr,
92               split->ib ? &ib : NULL,
93               !split->ib,
94               split->min_index,
95               split->max_index,
96               NULL, 0, NULL);
97
98   split->dstprim_nr = 0;
99   split->min_index = ~0;
100   split->max_index = 0;
101}
102
103
104static struct _mesa_prim *
105next_outprim(struct split_context *split)
106{
107   if (split->dstprim_nr == MAX_PRIM-1) {
108      flush_vertex(split);
109   }
110
111   {
112      struct _mesa_prim *prim = &split->dstprim[split->dstprim_nr++];
113      memset(prim, 0, sizeof(*prim));
114      return prim;
115   }
116}
117
118
119static void
120update_index_bounds(struct split_context *split,
121                    const struct _mesa_prim *prim)
122{
123   split->min_index = MIN2(split->min_index, prim->start);
124   split->max_index = MAX2(split->max_index, prim->start + prim->count - 1);
125}
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
133get_max_vertices(struct split_context *split,
134                 const struct _mesa_prim *prim)
135{
136   if ((prim->start > split->min_index &&
137        prim->start - split->min_index >= split->limit) ||
138       (prim->start < split->max_index &&
139        split->max_index - prim->start >= split->limit))
140      /* "prim" starts too far away from the old range. */
141      return 0;
142
143   return MIN2(split->min_index, prim->start) + split->limit - prim->start;
144}
145
146
147/* Break large primitives into smaller ones.  If not possible, convert
148 * the primitive to indexed and pass to split_elts().
149 */
150static void
151split_prims(struct split_context *split)
152{
153   GLuint i;
154
155   for (i = 0; i < split->nr_prims; i++) {
156      const struct _mesa_prim *prim = &split->prim[i];
157      GLuint first, incr;
158      GLboolean split_inplace =
159         _tnl_split_prim_inplace(prim->mode, &first, &incr);
160      GLuint available = get_max_vertices(split, prim);
161      GLuint count = prim->count - (prim->count - first) % incr;
162
163      if (prim->count < first)
164         continue;
165
166      if ((available < count && !split_inplace) ||
167          (available < first && split_inplace)) {
168         flush_vertex(split);
169         available = get_max_vertices(split, prim);
170      }
171
172      if (available >= count) {
173         struct _mesa_prim *outprim = next_outprim(split);
174
175         *outprim = *prim;
176         update_index_bounds(split, outprim);
177      }
178      else if (split_inplace) {
179         GLuint j, nr;
180
181         for (j = 0 ; j < count ;) {
182            GLuint remaining = count - j;
183            struct _mesa_prim *outprim = next_outprim(split);
184
185            nr = MIN2(available, remaining);
186            nr -= (nr - first) % incr;
187
188            outprim->mode = prim->mode;
189            outprim->begin = (j == 0 && prim->begin);
190            outprim->end = (nr == remaining && prim->end);
191            outprim->start = prim->start + j;
192            outprim->count = nr;
193            outprim->num_instances = prim->num_instances;
194            outprim->base_instance = prim->base_instance;
195
196            update_index_bounds(split, outprim);
197
198            if (nr == remaining) {
199               /* Finished */
200               j += nr;
201            }
202            else {
203               /* Wrapped the primitive */
204               j += nr - (first - incr);
205               flush_vertex(split);
206               available = get_max_vertices(split, prim);
207            }
208         }
209      }
210      else if (split->ib == NULL) {
211         /* XXX: could at least send the first max_verts off from the
212          * inplace buffers.
213          */
214
215         /* else convert to indexed primitive and pass to split_elts,
216          * which will do the necessary copying and turn it back into a
217          * vertex primitive for rendering...
218          */
219         struct _mesa_index_buffer ib;
220         struct _mesa_prim tmpprim;
221         GLuint *elts = malloc(count * sizeof(GLuint));
222         GLuint j;
223
224         for (j = 0; j < count; j++)
225            elts[j] = prim->start + j;
226
227         ib.count = count;
228         ib.index_size = 4;
229         ib.obj = split->ctx->Shared->NullBufferObj;
230         ib.ptr = elts;
231
232         tmpprim = *prim;
233         tmpprim.indexed = 1;
234         tmpprim.start = 0;
235         tmpprim.count = count;
236         tmpprim.num_instances = 1;
237         tmpprim.base_instance = 0;
238
239         flush_vertex(split);
240
241         _tnl_split_copy(split->ctx,
242                         split->array,
243                         &tmpprim, 1,
244                         &ib,
245                         split->draw,
246                         split->limits);
247
248         free(elts);
249      }
250      else {
251         flush_vertex(split);
252
253         _tnl_split_copy(split->ctx,
254                         split->array,
255                         prim, 1,
256                         split->ib,
257                         split->draw,
258                         split->limits);
259      }
260   }
261
262   flush_vertex(split);
263}
264
265
266void
267_tnl_split_inplace(struct gl_context *ctx,
268                   const struct tnl_vertex_array *arrays,
269                   const struct _mesa_prim *prim,
270                   GLuint nr_prims,
271                   const struct _mesa_index_buffer *ib,
272                   GLuint min_index,
273                   GLuint max_index,
274                   tnl_draw_func draw,
275                   const struct split_limits *limits)
276{
277   struct split_context split;
278
279   memset(&split, 0, sizeof(split));
280
281   split.ctx = ctx;
282   split.array = arrays;
283   split.prim = prim;
284   split.nr_prims = nr_prims;
285   split.ib = ib;
286
287   /* Empty interval, makes calculations simpler. */
288   split.min_index = ~0;
289   split.max_index = 0;
290
291   split.draw = draw;
292   split.limits = limits;
293   split.limit = ib ? limits->max_indices : limits->max_verts;
294
295   split_prims(&split);
296}
297
298
299