summaryrefslogblamecommitdiffstatshomepage
path: root/docs/source/techspecs/poly_manager.rst
blob: 305e1d7e315cb101be2758b56a7a6377765dab96 (plain) (tree)
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082

























































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































                                                                                                                             
Software 3D Rendering in MAME
=============================

.. contents:: :local:


Background
----------

Beginning in the late 1980s, many arcade games began incorporating hardware-rendered
3D graphics into their video. These 3D graphics are typically rendered from low-level
primitives into a frame buffer (usually double- or triple-buffered), then perhaps
combined with traditional tilemaps or sprites, before being presented to the player.

When it comes to emulating 3D games, there are two general approaches. The first
approach is to leverage modern 3D hardware by mapping the low-level primitives onto
modern equivalents. For a cross-platform emulator like MAME, this requires having an
API that is flexible enough to describe the primitives and all their associated
behaviors with high accuracy. It also requires the emulator to be able to read back
from the rendered frame buffer (since many games do this) and combine it with other
elements, in a way that is properly synchronized with background rendering.

The alternative approach is to render the low-level primitives directly in software.
This has the advantage of being able to achieve pretty much any behavior exhibited by
the original hardware, but at the cost of speed. In MAME, since all emulation happens
on one thread, this is particularly painful. However, just as with the 3D hardware
approach, in theory a software-based approach could be spun off to other threads to
handle the work, as long as mechanisms were present to synchronize when necessary,
for example, when reading/writing directly to/from the frame buffer.

For the time being, MAME has opted for the second approach, leveraging a templated
helper class called **poly_manager** to handle common situations.


Concepts
--------

At its core, **poly_manager** is a mechanism to support multi-threaded rendering of
low-level 3D primitives. Callers provide **poly_manager** with a set of *vertices* for a
primitive plus a *render callback*. **poly_manager** breaks the primitive into
clipped scanline *extents* and distributes the work among a pool of *worker
threads*. The render callback is then called on the worker thread for each extent,
where game-specific logic can do whatever needs to happen to render the data.

One key responsibility that **poly_manager** takes care of is ensuring order. Given a
pool of threads and a number of work items to complete, it is important that—at least
within a given scanline—all work is performed serially in order. The basic approach is
to assign each extent to a *bucket* based on the Y coordinate. **poly_manager** then ensures
that only one worker thread at a time is responsible for processing work in a given bucket.

Vertices in **poly_manager** consist of simple 2D X and Y *coordinates*, plus zero or
more additional *iterated parameters*. These iterated parameters can be anything: intensity
values for lighting; RGB(A) colors for Gouraud shading; normalized U, V coordinates for
texture mapping; 1/Z values for Z buffering; etc. Iterated parameters, regardless of what
they represent, are interpolated linearly across the primitive in screen space and provided
as part of the extent to the render callback.


ObjectType
~~~~~~~~~~

When creating a **poly_manager** class, you must provide it a special type that you define,
known as **ObjectType**.

Because rendering happens asynchronously on worker threads, the idea is that the
**ObjectType** class will hold a snapshot of all the relevant data needed for rendering.
This allows the main thread to proceed—potentially modifying some of the relevant state—while
rendering happens elsewhere.

In theory, we could allocate a new **ObjectType** class for each primitive rendered;
however, that would be rather inefficient. It is quite common to set up the rendering
state and then render several primitives using the same state.

For this reason, **poly_manager** maintains an internal array of **ObjectType** objects and
keeps a copy of the last **ObjectType** used. Before submitting a new primitive, callers
can see if the rendering state has changed. If it has, it can ask **poly_manager** to allocate
a new **ObjectType** class and fill it in. When the primitive is submitted for rendering, the
most recently allocated **ObjectType** instance is implicitly captured and provided to the
render callbacks.

For more complex scenarios, where data might change even more infrequently, there is a
**poly_array** template, which can be used to manage data in a similar way. In fact,
internally **poly_manager** uses the **poly_array** class to manage its **ObjectType**
allocations. More information on the **poly_array** class is provided later.



Primitives
~~~~~~~~~~

**poly_manager** supports several different types of primitives:

* The most commonly-used primitive in **poly_manager** is the *triangle*, which has the
  nice property that iterated parameters have constant deltas across the full surface.
  Arbitrary-length *triangle fans* and *triangle strips* are also supported.

* In addition to triangles, **poly_manager** also supports *polygons* with an arbitrary
  number of vertices. The list of vertices is expected to be in either clockwise or
  anticlockwise order. **poly_manager** will walk the edges to compute deltas across
  each extent.

* As a special case, **poly_manager** supports a *tile* primitive, which is a simple quad
  defined by two vertices, a top-left vertex and a bottom-right vertex. Like triangles,
  tiles have constant iterated parameter deltas across their surface.

* Finally, **poly_manager** supports a fully custom mechanism where the caller provides
  a list of extents that are more or less fed directly to the worker threads.
  This is useful if emulating a system that has unusual primitives or requires highly
  specific behaviors for its edges.


Synchronization
~~~~~~~~~~~~~~~

One of the key requirements of providing an asynchronous rendering mechanism is
synchronization. Synchronization in **poly_manager** is super simple: just
call the ``wait()`` function.

There are several common reasons for issuing a wait:

* At display time, the pixel data must be copied to the screen. If any primitives were
  queued which touch the portion of the display that is going to be shown, you need to
  wait for rendering to be complete before copying. Note that this wait may not be
  strictly necessary in some situations (for example, a triple-buffered system).

* If the emulated system has a mechanism to read back from the framebuffer after
  rendering, then a wait must be issued prior to the read in order to ensure that
  asynchronous rendering is complete.

* If the emulated system modifies any state that is not cached in the **ObjectType**
  or elsewhere (for example, texture memory), then a wait must be issued to ensure
  that pending primitives which might consume that state have finished their work.

* If the emulated system can use a previous render target as, say, the texture source
  for a new primitive, then submitting the second primitive must wait until the first
  completes. **poly_manager** provides no internal mechanism to help detect this, so it
  is on the caller to determine when or if this is necessary.

Because the wait operation knows after it is done that all rendering is complete,
**poly_manager** also takes this opportunity to reclaim all memory allocated for its
internal structures, as well as memory allocated for **ObjectType** structures. Thus it is
important that you don’t hang onto any **ObjectType** pointers after a wait is called.


The poly_manager class
----------------------

In most applications, **poly_manager** is not used directly, but rather serves as
the base class for a more complete rendering class. The **poly_manager** class
itself is a template::

    template<typename BaseType, class ObjectType, int MaxParams, u8 Flags = 0>
    class poly_manager;

and the template parameters are:

* **BaseType** is the type used internally for coordinates and iterated parameters, and
  should generally be either ``float`` or ``double``. In theory, a fixed-point integral
  type could also be used, though the math logic has not been designed for that, so you
  may encounter problems.

* **ObjectType** is the user-defined per-object data structure described above.
  Internally, **poly_manager** will manage a **poly_array** of these, and a pointer to
  the most-recently allocated one at the time a primitive is submitted will be implicitly
  passed to the render callback for each corresponding extent.

* **MaxParams** is the maximum number of iterated parameters that may be specified in a
  vertex. Iterated parameters are generic and treated identically, so the mapping of
  parameter indices is completely up to the contract between the caller and the render
  callback. It is permitted for **MaxParams** to be 0.

* **Flags** is zero or more of the following flags:

  - POLY_FLAG_NO_WORK_QUEUE — specify this flag to disable asynchronous rendering; this
    can be useful for debugging. When this option is enabled, all primitives are queued
    and then processed in order on the calling thread when ``wait()`` is called on the
    **poly_manager** class.

  - POLY_FLAG_NO_CLIPPING — specify this if you want **poly_manager** to skip its
    internal clipping. Use this if your render callbacks do their own clipping, or if
    the caller always handles clipping prior to submitting primitives.


Types & Constants
~~~~~~~~~~~~~~~~~

vertex_t
++++++++

Within the **poly_manager** class, you’ll find a **vertex_t** type that describes a
single vertex. All primitive drawing methods accept 2 or more of these **vertex_t**
objects. The **vertex_t** includes the X and Y coordinates along with an array of
iterated parameter values at that vertex::

    struct vertex_t
    {
        vertex_t() { }
        vertex_t(BaseType _x, BaseType _y) { x = _x; y = _y; }

        BaseType x, y;                          // X, Y coordinates
        std::array<BaseType, MaxParams> p;      // iterated parameters
    };

Note that **vertex_t** itself is defined in terms of the **BaseType** and **MaxParams**
template values of the owning **poly_manager** class.

All of **poly_manager**’s primitives operate in screen space, where (0,0) represents the
top-left corner of the top-left pixel, and (0.5,0.5) represents the center of that pixel.
Left and top pixel values are inclusive, while right and bottom pixel values are exclusive.

Thus, a *tile* rendered from (2,2)-(4,3) will completely cover 2 pixels: (2,2) and (3,2).

When calling a primitive drawing method, the iterated parameter array **p** need not be
completely filled out. The number of valid iterated parameter values is specified as a
template parameter to the primitive drawing methods, so only that many parameters need to
actually be populated in the **vertex_t** structures that are passed in.


extent_t
++++++++

**poly_manager** breaks primitives into extents, which are contiguous horizontal spans
contained within a single scanline. These extents are then distributed to worker threads,
who will call the render callback with information on how to render each extent. The
**extent_t** type describes one such extent, providing the bounding X coordinates along with
an array of iterated parameter start values and deltas across the span::

    struct extent_t
    {
        struct param_t
        {
            BaseType start;                     // parameter value at start
            BaseType dpdx;                      // dp/dx relative to start
        };
        int16_t startx, stopx;                  // starting (inclusive)/ending (exclusive) endpoints
        std::array<param_t, MaxParams> param;   // array of parameter start/deltas
        void *userdata;                         // custom per-span data
    };

For each iterated parameter, the **start** value contains the value at the left side of
the span. The **dpdx** value contains the change of the parameter’s value per X coordinate.

There is also a **userdata** field in the **extent_t** structure, which is not normally used,
except when performing custom rendering.


render_delegate
+++++++++++++++

When rendering a primitive, in addition to the vertices, you must also provide a
**render_delegate** callback of the form::

  void render(int32_t y, extent_t const &extent, ObjectType const &object, int threadid)

This callback is responsible for the actual rendering. It will be called at a later time,
likely on a different thread, for each extent. The parameters passed are:

* **y** is the Y coordinate (scanline) of the current extent.

* **extent** is a reference to a **extent_t** structure, described above, which specifies for
  this extent the start/stop X values along with the start/delta values for each iterated
  parameter.

* **object** is a reference to the most recently allocated **ObjectType** at the time the
  primitive was submitted for rendering; in theory it should contain most of not all of the
  necessary data to perform rendering.

* **threadid** is a unique ID indicating the index of the thread you’re running on; this value
  is useful if you are keeping any kind of statistics and don’t want to add contention over
  shared values. In this situation, you can allocate **WORK_MAX_THREADS** instances of your
  data and update the instance for the **threadid** you are passed. When you want to display
  the statistics, the main thread can accumulate and reset the data from all threads when it’s
  safe to do so (e.g., after a wait).


Methods
~~~~~~~

poly_manager
++++++++++++
::

    poly_manager(running_machine &machine);

The **poly_manager** constructor takes just one parameter, a reference to the
**running_machine**. This grants **poly_manager** access to the work queues needed for
multithreaded running.

wait
++++
::

    void wait(char const *debug_reason = "general");

Calling ``wait()`` stalls the calling thread until all outstanding rendering is complete:

* **debug_reason** is an optional parameter specifying the reason for the wait. It is
  useful if the compile-time constant **TRACK_POLY_WAITS** is enabled, as it will print a
  summary of wait times and reasons at the end of execution.

**Return value:** none.

object_data
+++++++++++
::

    objectdata_array &object_data();

This method just returns a reference to the internally-maintained **poly_array** of the
**ObjectType** you specified when creating **poly_manager**. For most applications, the
only interesting thing to do with this object is call the ``next()`` method to allocate
a new object to fill out.

**Return value:** reference to a **poly_array** of **ObjectType**.

register_poly_array
+++++++++++++++++++
::

    void register_poly_array(poly_array_base &array);

For advanced applications, you may choose to create your own **poly_array** objects to
manage large chunks of infrequently-changed data, such a palettes. After each ``wait()``,
**poly_manager** resets all the **poly_array** objects it knows about in order to reclaim all
outstanding allocated memory. By registering your **poly_array** objects here, you can ensure
that your arrays will also be reset after an ``wait()`` call.

**Return value:** none.

render_tile
+++++++++++
::

    template<int ParamCount>
    uint32_t render_tile(rectangle const &cliprect, render_delegate callback,
                         vertex_t const &v1, vertex_t const &v2);

This method enqueues a single *tile* primitive for rendering:

* **ParamCount** is the number of live values in the iterated parameter array within each
  **vertex_t** provided; it must be no greater than the **MaxParams** value specified in the
  **poly_manager** template instantiation.

* **cliprect** is a reference to a clipping rectangle. All pixels and parameter values are
  clipped to stay within these bounds before being added to the work queues for rendering,
  unless **POLY_FLAG_NO_CLIPPING** was specified as a flag parameter to **poly_manager**.

* **callback** is the render callback delegate that will be called to render each extent.

* **v1** contains the coordinates and iterated parameters for the top-left corner of the tile.

* **v2** contains the coordinates and iterated parameters for the bottom-right corner of the tile.

**Return value:** the total number of clipped pixels represented by the enqueued extents.

render_triangle
+++++++++++++++
::

    template<int ParamCount>
    uint32_t render_triangle(rectangle const &cliprect, render_delegate callback,
                             vertex_t const &v1, vertex_t const &v2, vertex_t const &v3);

This method enqueues a single *triangle* primitive for rendering:

* **ParamCount** is the number of live values in the iterated parameter array within each
  **vertex_t** provided; it must be no greater than the **MaxParams** value specified in the
  **poly_manager** template instantiation.

* **cliprect** is a reference to a clipping rectangle. All pixels and parameter values are
  clipped to stay within these bounds before being added to the work queues for rendering,
  unless **POLY_FLAG_NO_CLIPPING** was specified as a flag parameter to **poly_manager**.

* **callback** is the render callback delegate that will be called to render each extent.

* **v1**, **v2**, **v3** contain the coordinates and iterated parameters for each vertex
  of the triangle.

**Return value:** the total number of clipped pixels represented by the enqueued extents.

render_triangle_fan
+++++++++++++++++++
::

    template<int ParamCount>
    uint32_t render_triangle_fan(rectangle const &cliprect, render_delegate callback,
                                 int numverts, vertex_t const *v);

This method enqueues one or more *triangle* primitives for rendering, specified in fan order:

* **ParamCount** is the number of live values in the iterated parameter array within each
  **vertex_t** provided; it must be no greater than the **MaxParams** value specified in the
  **poly_manager** template instantiation.

* **cliprect** is a reference to a clipping rectangle. All pixels and parameter values are
  clipped to stay within these bounds before being added to the work queues for rendering,
  unless **POLY_FLAG_NO_CLIPPING** was specified as a flag parameter to **poly_manager**.

* **callback** is the render callback delegate that will be called to render each extent.

* **numverts** is the total number of vertices provided; it must be at least 3.

* **v** is a pointer to an array of **vertex_t** objects containing the coordinates and iterated
  parameters for all the triangles, in fan order. This means that the first vertex is fixed.
  So if 5 vertices are provided, indicating 3 triangles, the vertices used will be:
  (0,1,2) (0,2,3) (0,3,4)

**Return value:** the total number of clipped pixels represented by the enqueued extents.

render_triangle_strip
+++++++++++++++++++++
::

    template<int ParamCount>
    uint32_t render_triangle_strip(rectangle const &cliprect, render_delegate callback,
                                   int numverts, vertex_t const *v);

This method enqueues one or more *triangle* primitives for rendering, specified in strip order:

* **ParamCount** is the number of live values in the iterated parameter array within each
  **vertex_t** provided; it must be no greater than the **MaxParams** value specified in the
  **poly_manager** template instantiation.

* **cliprect** is a reference to a clipping rectangle. All pixels and parameter values are
  clipped to stay within these bounds before being added to the work queues for rendering,
  unless **POLY_FLAG_NO_CLIPPING** was specified as a flag parameter to **poly_manager**.

* **callback** is the render callback delegate that will be called to render each extent.

* **numverts** is the total number of vertices provided; it must be at least 3.

* **v** is a pointer to an array of **vertex_t** objects containing the coordinates and iterated
  parameters for all the triangles, in strip order.
  So if 5 vertices are provided, indicating 3 triangles, the vertices used will be:
  (0,1,2) (1,2,3) (2,3,4)

**Return value:** the total number of clipped pixels represented by the enqueued extents.

render_polygon
++++++++++++++
::

    template<int NumVerts, int ParamCount>
    uint32_t render_polygon(rectangle const &cliprect, render_delegate callback, vertex_t const *v);

This method enqueues a single *polygon* primitive for rendering:

* **NumVerts** is the number of vertices in the polygon.

* **ParamCount** is the number of live values in the iterated parameter array within each
  **vertex_t** provided; it must be no greater than the **MaxParams** value specified in the
  **poly_manager** template instantiation.

* **cliprect** is a reference to a clipping rectangle. All pixels and parameter values are
  clipped to stay within these bounds before being added to the work queues for rendering,
  unless **POLY_FLAG_NO_CLIPPING** was specified as a flag parameter to **poly_manager**.

* **callback** is the render callback delegate that will be called to render each extent.

* **v** is a pointer to an array of **vertex_t** objects containing the coordinates and iterated
  parameters for the polygon. Vertices are assumed to be in either clockwise or anticlockwise
  order.

**Return value:** the total number of clipped pixels represented by the enqueued extents.

render_extents
++++++++++++++
::

    template<int ParamCount>
    uint32_t render_extents(rectangle const &cliprect, render_delegate callback,
                            int startscanline, int numscanlines, extent_t const *extents);

This method enqueues custom extents directly:

* **ParamCount** is the number of live values in the iterated parameter array within each
  **vertex_t** provided; it must be no greater than the **MaxParams** value specified in the
  **poly_manager** template instantiation.

* **cliprect** is a reference to a clipping rectangle. All pixels and parameter values are
  clipped to stay within these bounds before being added to the work queues for rendering,
  unless **POLY_FLAG_NO_CLIPPING** was specified as a flag parameter to **poly_manager**.

* **callback** is the render callback delegate that will be called to render each extent.

* **startscanline** is the Y coordinate of the first extent provided.

* **numscanlines** is the number of extents provided.

* **extents** is a pointer to an array of **extent_t** objects containing the start/stop
  X coordinates and iterated parameters. The **userdata** field of the source extents is
  copied to the target as well (this field is otherwise unused for all other types of
  rendering).

**Return value:** the total number of clipped pixels represented by the enqueued extents.

zclip_if_less
+++++++++++++
::

    template<int ParamCount>
    int zclip_if_less(int numverts, vertex_t const *v, vertex_t *outv, BaseType clipval);

This method is a helper method to clip a polygon against a provided Z value. It assumes
that the first iterated parameter in **vertex_t** represents the Z coordinate. If any edge
crosses the Z plane represented by **clipval** that edge is clipped.

* **ParamCount** is the number of live values in the iterated parameter array within each
  **vertex_t** provided; it must be no greater than the **MaxParams** value specified in the
  **poly_manager** template instantiation.

* **numverts** is the number of vertices in the input array.

* **v** is a pointer to the input array of **vertex_t** objects.

* **outv** is a pointer to the output array of **vertex_t** objects. **v** and **outv**
  cannot overlap or point to the same memory.

* **clipval** is the value to compare parameter 0 against for clipping.

**Return value:** the number of output vertices written to **outv**.
Note that by design it is possible for this method to produce more vertices than the
input array, so callers should ensure there is enough room in the output buffer to
accommodate this.


Example Renderer
----------------

Here is a complete example of how to create a software 3D renderer using **poly_manager**.
Our example renderer will only handle flat and Gouraud-shaded triangles with depth (Z)
buffering.

Types
~~~~~

The first thing we need to define is our *externally-visible* vertex format, which is distinct
from the internal **vertex_t** that **poly_manager** will define. In theory you could
use **vertex_t** directly, but the generic nature of **poly_manager**’s iterated parameters
make it awkward::

    struct example_vertex
    {
        float x, y, z;      // X,Y,Z coordinates
        rgb_t color;        // color at this vertex
    };

Next we define the **ObjectType** needed by **poly_manager**. For our simple case, we
define an **example_object_data** struct that consists of pointers to our rendering buffers,
plus a couple of fixed values that are consumed in some cases. More complex renderers would
typically have many more object-wide parameters defined here::

    struct example_object_data
    {
        bitmap_rgb32 *dest;    // pointer to the rendering bitmap
        bitmap_ind16 *depth;   // pointer to the depth bitmap
        rgb_t color;           // overall color (for clearing and flat shaded case)
        uint16_t depthval;     // fixed depth v alue (for clearing)
    };

Now it’s time to define our renderer class, which we derive from **poly_manager**. As
template parameters we specify ``float`` as the base type for our data, since that will
be enough accuracy for this example, and we also provide our **example_object_data** as
the **ObjectType** class, plus the maximum number of iterated parameters our renderer
will ever need (4 in this case)::

    class example_renderer : public poly_manager<float, example_object_data, 4>
    {
    public:
        example_renderer(running_machine &machine, uint32_t width, uint32_t height);

        bitmap_rgb32 *swap_buffers();

        void clear_buffers(rgb_t color, uint16_t depthval);
        void draw_triangle(example_vertex const *verts);

    private:
        static uint16_t ooz_to_depthval(float ooz);

        void draw_triangle_flat(example_vertex const *verts);
        void draw_triangle_gouraud(example_vertex const *verts);

        void render_clear(int32_t y, extent_t const &extent, example_object_data const &object, int threadid);
        void render_flat(int32_t y, extent_t const &extent, example_object_data const &object, int threadid);
        void render_gouraud(int32_t y, extent_t const &extent, example_object_data const &object, int threadid);

        int m_draw_buffer;
        bitmap_rgb32 m_display[2];
        bitmap_ind16 m_depth;
    };


Constructor
~~~~~~~~~~~

The constructor for our example renderer just initializes **poly_manager** and allocates
the rendering and depth buffers::

    example_renderer::example_renderer(running_machine &machine, uint32_t width, uint32_t height) :
        poly_manager(machine),
        m_draw_buffer(0)
    {
        // allocate two display buffers and a depth buffer
        m_display[0].allocate(width, height);
        m_display[1].allocate(width, height);
        m_depth.allocate(width, height);
    }


swap_buffers
~~~~~~~~~~~~

The first interesting method in our renderer is ``swap_buffers()``, which returns a pointer to
the buffer we’ve been drawing to, and sets up the other buffer as the new drawing target. The
idea is that the display update handler will call this method to get ahold of the bitmap to
display to the user::

    bitmap_rgb32 *example_renderer::swap_buffers()
    {
        // wait for any rendering to complete before returning the buffer
        wait("swap_buffers");

        // return the current draw buffer and then switch to the other
        // for future drawing
        bitmap_rgb32 *result = &m_display[m_draw_buffer];
        m_draw_buffer ^= 1;
        return result;
    }

The most important thing here to note here is the call to **poly_manager**’s ``wait()``, which
will block the current thread until all rendering is complete. This is important because
otherwise the caller may receive a bitmap that is still being drawn to, leading to torn
or corrupt visuals.


clear_buffers
~~~~~~~~~~~~~

One of the most common operations to perform when doing 3D rendering is to initialize or
clear the display and depth buffers to a known value. This method below leverages
the *tile* primitive to render a rectangle over the screen by passing in (0,0) and (width,height)
for the two vertices.

Because the color and depth values to clear the buffer to are constant, they are stored in
a freshly-allocated **example_object_data** object, along with a pointer to the buffers in
question. The ``render_tile()`` call is made with a ``<0>`` suffix indicating that there are
no iterated parameters to worry about::

    void example_renderer::clear_buffers(rgb_t color, uint16_t depthval)
    {
        // allocate object data and populate it with information needed
        example_object_data &object = object_data().next();
        object.dest = &m_display[m_draw_buffer];
        object.depth = &m_depth;
        object.color = color;
        object.depthval = depthval;

        // top,left coordinate is always (0,0)
        vertex_t topleft;
        topleft.x = 0;
        topleft.y = 0;

        // bottom,right coordinate is (width,height)
        vertex_t botright;
        botright.x = m_display[0].width();
        botright.y = m_display[0].height();

        // render as a tile with 0 iterated parameters
        render_tile<0>(m_display[0].cliprect(),
                       render_delegate(&example_renderer::render_clear, this),
                       topleft, botright);
    }

The render callback provided to ``render_tile()`` is also defined (privately) in our class,
and handles a single span. Note how the rendering parameters are extracted from the
**example_object_data** struct provided::

    void example_renderer::render_clear(int32_t y, extent_t const &extent, example_object_data const &object, int threadid)
    {
        // get pointers to the start of the depth buffer and destination scanlines
        uint16_t *depth = &object.depth->pix(y);
        uint32_t *dest = &object.dest->pix(y);

        // loop over the full extent and just store the constant values from the object
        for (int x = extent.startx; x < extent.stopx; x++)
        {
            dest[x] = object.color;
            depth[x] = object.depthval;
        }
    }

Another important point to make is that the X coordinates provided by extent struct are
inclusive of startx but exclusive of stopx. Clipping is performed ahead of time so that
the render callback can focus on laying down pixels as quickly as possible with minimal
overhead.


draw_triangle
~~~~~~~~~~~~~

Next up, we have our actual triangle rendering function, which will draw a single triangle
given an array of three vertices provided in the external **example_vertex** format::

    void example_renderer::draw_triangle(example_vertex const *verts)
    {
        // flat shaded case
        if (verts[0].color == verts[1].color && verts[0].color == verts[2].color)
            draw_triangle_flat(verts);
        else
            draw_triangle_gouraud(verts);
    }

Because it is simpler and faster to render a flat shaded triangle, the code checks to see
if the colors are the same on all three vertices. If they are, we call through to a special
flat-shaded case, otherwise we process it as a full Gouraud-shaded triangle.

This is a common technique to optimize rendering performance: identify special cases that
reduce the per-pixel work, and route them to separate render callbacks that are optimized
for that special case.


draw_triangle_flat
~~~~~~~~~~~~~~~~~~

Here’s the setup code for rendering a flat-shaded triangle::

    void example_renderer::draw_triangle_flat(example_vertex const *verts)
    {
        // allocate object data and populate it with information needed
        example_object_data &object = object_data().next();
        object.dest = &m_display[m_draw_buffer];
        object.depth = &m_depth;

        // in this case the color is constant and specified in the object data
        object.color = verts[0].color;

        // copy X, Y, and 1/Z into poly_manager vertices
        vertex_t v[3];
        for (int vertnum = 0; vertnum < 3; vertnum++)
        {
            v[vertnum].x = verts[vertnum].x;
            v[vertnum].y = verts[vertnum].y;
            v[vertnum].p[0] = 1.0f / verts[vertnum].z;
        }

        // render the triangle with 1 iterated parameter (1/Z)
        render_triangle<1>(m_display[0].cliprect(),
                            render_delegate(&example_renderer::render_flat, this),
                            v[0], v[1], v[2]);
    }

First, we put the fixed color into the **example_object_data** directly, and then fill
out three **vertex_t** objects with the X and Y coordinates in the usual spot, and 1/Z
as our one and only iterated parameter. (We use 1/Z here because iterated parameters are
interpolated linearly in screen space. Z is not linear in screen space, but 1/Z is due to
perspective correction.)

Our flat-shaded case then calls ``render_trangle`` specifying ``<1>`` iterated parameter to
interpolate, and pointing to a special-case flat render callback::

    void example_renderer::render_flat(int32_t y, extent_t const &extent, example_object_data const &object, int threadid)
    {
        // get pointers to the start of the depth buffer and destination scanlines
        uint16_t *depth = &object.depth->pix(y);
        uint32_t *dest = &object.dest->pix(y);

        // get the starting 1/Z value and the delta per X
        float ooz = extent.param[0].start;
        float doozdx = extent.param[0].dpdx;

        // iterate over the extent
        for (int x = extent.startx; x < extent.stopx; x++)
        {
            // convert the 1/Z value into an integral depth value
            uint16_t depthval = ooz_to_depthval(ooz);

            // if closer than the current pixel, copy the color and depth value
            if (depthval < depth[x])
            {
                dest[x] = object.color;
                depth[x] = depthval;
            }

            // regardless, update the 1/Z value for the next pixel
            ooz += doozdx;
        }
    }

This render callback is a bit more involved than the clearing case.

First, we have an iterated parameter (1/Z) to deal with, whose starting and X-delta
values we extract from the extent before the start of the inner loop.

Second, we perform depth buffer testing, using ``ooz_to_depthval()`` as a helper
to transform the floating-point 1/Z value into a 16-bit integer. We compare this value against
the current depth buffer value, and only store the pixel/depth value if it’s less.

At the end of each iteration, we advance the 1/Z value by the X-delta in preparation for the
next pixel.

draw_triangle_gouraud
~~~~~~~~~~~~~~~~~~~~~

Finally we get to the code for the full-on Gouraud-shaded case::

    void example_renderer::draw_triangle_gouraud(example_vertex const *verts)
    {
        // allocate object data and populate it with information needed
        example_object_data &object = object_data().next();
        object.dest = &m_display[m_draw_buffer];
        object.depth = &m_depth;

        // copy X, Y, 1/Z, and R,G,B into poly_manager vertices
        vertex_t v[3];
        for (int vertnum = 0; vertnum < 3; vertnum++)
        {
            v[vertnum].x = verts[vertnum].x;
            v[vertnum].y = verts[vertnum].y;
            v[vertnum].p[0] = 1.0f / verts[vertnum].z;
            v[vertnum].p[1] = verts[vertnum].color.r();
            v[vertnum].p[2] = verts[vertnum].color.g();
            v[vertnum].p[3] = verts[vertnum].color.b();
        }

        // render the triangle with 4 iterated parameters (1/Z, R, G, B)
        render_triangle<4>(m_display[0].cliprect(),
                            render_delegate(&example_renderer::render_gouraud, this),
                            v[0], v[1], v[2]);
    }

Here we have 4 iterated parameters: the 1/Z depth value, plus red, green, and blue,
stored as floating point values. We call ``render_triangle()`` with ``<4>`` as the
number of iterated parameters to process, and point to the full Gouraud render callback::

    void example_renderer::render_gouraud(int32_t y, extent_t const &extent, example_object_data const &object, int threadid)
    {
        // get pointers to the start of the depth buffer and destination scanlines
        uint16_t *depth = &object.depth->pix(y);
        uint32_t *dest = &object.dest->pix(y);

        // get the starting 1/Z value and the delta per X
        float ooz = extent.param[0].start;
        float doozdx = extent.param[0].dpdx;

        // get the starting R,G,B values and the delta per X as 8.24 fixed-point values
        uint32_t r = uint32_t(extent.param[1].start * float(1 << 24));
        uint32_t drdx = uint32_t(extent.param[1].dpdx * float(1 << 24));
        uint32_t g = uint32_t(extent.param[2].start * float(1 << 24));
        uint32_t dgdx = uint32_t(extent.param[2].dpdx * float(1 << 24));
        uint32_t b = uint32_t(extent.param[3].start * float(1 << 24));
        uint32_t dbdx = uint32_t(extent.param[3].dpdx * float(1 << 24));

        // iterate over the extent
        for (int x = extent.startx; x < extent.stopx; x++)
        {
            // convert the 1/Z value into an integral depth value
            uint16_t depthval = ooz_to_depthval(ooz);

            // if closer than the current pixel, assemble the color
            if (depthval < depth[x])
            {
                dest[x] = rgb_t(r >> 24, g >> 24, b >> 24);
                depth[x] = depthval;
            }

            // regardless, update the 1/Z and R,G,B values for the next pixel
            ooz += doozdx;
            r += drdx;
            g += dgdx;
            b += dbdx;
        }
    }

This follows the same pattern as the flat-shaded callback, except we have 4 iterated parameters
to step through.

Note that even though the iterated parameters are of ``float`` type, we convert the
color values to fixed-point integers when iterating over them. This saves us doing 3
float-to-int conversions each pixel. The original RGB values were 0-255, so interpolation
can only produce values in the 0-255 range. Thus we can use 24 bits of a 32-bit integer as
the fraction, which is plenty accurate for this case.


Advanced Topic: the poly_array class
------------------------------------

**poly_array** is a template class that is used to manage a dynamically-sized vector of
objects whose lifetime starts at allocation and ends when ``reset()`` is called. The
**poly_manager** class uses several **poly_array** objects internally, including one for
allocated **ObjectType** data, one for each primitive rendered, and one for holding all
allocated extents.

**poly_array** has an additional property where after a reset it retains a copy of the most
recently allocated object. This ensures that callers can always call ``last()`` and get
a valid object, even immediately after a reset.

The **poly_array** class requires two template parameters::

    template<class ArrayType, int TrackingCount>
    class poly_array;

These parameters are:

* **ArrayType** is the type of object you wish to allocate and manage.

* **TrackingCount** is the number of objects you wish to preserve after a reset. Typically
  this value is either 0 (you don’t care to track any objects) or 1 (you only need one
  object); however, if you are using **poly_array** to manage a shared collection of
  objects across several independent consumers, it can be higher. See below for an example
  where this might be handy.

Note that objects allocated by **poly_array** are owned by **poly_array** and will be
automatically freed upon exit.

**poly_array** is optimized for use in high frequency multi-threaded systems. Therefore,
one added feature of the class is that it rounds the allocation size of **ArrayType** to
the nearest cache line boundary, on the assumption that neighboring entries could be
accessed by different cores simultaneously. Keeping each **ArrayType** object in its
own cache line ensures no false sharing performance impacts.

Currently, **poly_array** has no mechanism to determine cache line size at runtime, so
it presumes that 64 bytes is a typical cache line size, which is true for most x64 and ARM
chips as of 2021. This value can be altered by changing the **CACHE_LINE_SHIFT** constant
defined at the top of the class.

Objects allocated by **poly_array** are created in 64k chunks. At construction time, one
chunk’s worth of objects is allocated up front. The chunk size is controlled by the
**CHUNK_GRANULARITY** constant defined at the top of the class.

As more objects are allocated, if **poly_array** runs out of space, it will dynamically
allocate more. This will produce discontiguous chunks of objects until the next ``reset()``
call, at which point **poly_array** will reallocate all the objects into a contiguous
vector once again.

For the case where **poly_array** is used to manage a shared pool of objects, it can be
configured to retain multiple most recently allocated items by using a **TrackingCount**
greater than 1. For example, if **poly_array** is managing objects for two texture units,
then it can set **TrackingCount** equal to 2, and pass the index of the texture unit in
calls to ``next()`` and ``last()``. After a reset, **poly_array** will remember the most
recently allocated object for each of the units independently.


Methods
~~~~~~~

poly_array
++++++++++
::

    poly_array();

The **poly_array** contructor requires no parameters and simply pre-allocates one
chunk of objects in preparation for future allocations.

count
+++++
::

	u32 count() const;

**Return value:** the number of objects currently allocated.

max
+++
::

	u32 max() const;

**Return value:** the maximum number of objects ever allocated at one time.

itemsize
++++++++
::

	size_t itemsize() const;

**Return value:** the size of an object, rounded up to the nearest cache line boundary.

allocated
+++++++++
::

	u32 allocated() const;

**Return value:** the number of objects that fit within what’s currently been allocated.

byindex
+++++++
::

	ArrayType &byindex(u32 index);

Returns a reference to an object in the array by index. Equivalent to [**index**] on a
normal array:

* **index** is the index of the item you wish to reference.

**Return value:** a reference to the object in question. Since a reference is returned,
it is your responsibility to ensure that **index** is less than ``count()`` as there
is no mechanism to return an invalid result.

contiguous
++++++++++
::

	ArrayType *contiguous(u32 index, u32 count, u32 &chunk);

Returns a pointer to the base of a contiguous section of **count** items starting at
**index**. Because **poly_array** dynamically resizes, it may not be possible to access
all **count** objects contiguously, so the number of actually contiguous items is
returned in **chunk**:

* **index** is the index of the first item you wish to access contiguously.

* **count** is the number of items you wish to access contiguously.

* **chunk** is a reference to a variable that will be set to the actual number of
  contiguous items available starting at **index**. If **chunk** is less than **count**,
  then the caller should process the **chunk** items returned, then call ``countiguous()``
  again at (**index** + **chunk**) to access the rest.

**Return value:** a pointer to the first item in the contiguous chunk. No range checking
is performed, so it is your responsibility to ensure that **index** + **count** is less
than or equal to ``count()``.

indexof
+++++++
::

	int indexof(ArrayType &item) const;

Returns the index within the array of the given item:

* **item** is a reference to an item in the array.

**Return value:** the index of the item. It should always be the case that::

    array.indexof(array.byindex(index)) == index

reset
+++++
::

	void reset();

Resets the **poly_array** by semantically deallocating all objects. If previous allocations
created a discontiguous array, a fresh vector is allocated at this time so that future
allocations up to the same level will remain contiguous.

Note that the **ArrayType** destructor is *not* called on objects as they are deallocated.

**Return value:** none.

next
++++
::

	ArrayType &next(int tracking_index = 0);

Allocates a new object and returns a reference to it. If there is not enough space for
a new object in the current array, a new discontiguous array is created to hold it:

* **tracking_index** is the tracking index you wish to assign the new item to. In the
  common case this is 0, but could be non-zero if using a **TrackingCount** greater than 1.

**Return value:** a reference to the object. Note that the placement new operator is
called on this object, so the default **ArrayType** constructor will be invoked here.

last
++++
::

	ArrayType &last(int tracking_index = 0) const;

Returns a reference to the last object allocated:

* **tracking_index** is the tracking index whose object you want. In the
  common case this is 0, but could be non-zero if using a **TrackingCount** greater than 1.
  **poly_array** remembers the most recently allocated object independently for each
  **tracking_index**.

**Return value:** a reference to the last allocated object.