// license:BSD-3-Clause
// copyright-holders:Ville Linde, Aaron Giles
/***************************************************************************
poly.h
Polygon helper routines.
****************************************************************************
Pixel model:
(0.0,0.0) (1.0,0.0) (2.0,0.0) (3.0,0.0)
+---------------+---------------+---------------+
| | | |
| | | |
| (0.5,0.5) | (1.5,0.5) | (2.5,0.5) |
| * | * | * |
| | | |
| | | |
(0.0,1.0) (1.0,1.0) (2.0,1.0) (3.0,1.0)
+---------------+---------------+---------------+
| | | |
| | | |
| (0.5,1.5) | (1.5,1.5) | (2.5,1.5) |
| * | * | * |
| | | |
| | | |
| | | |
+---------------+---------------+---------------+
(0.0,2.0) (1.0,2.0) (2.0,2.0) (3.0,2.0)
***************************************************************************/
#ifndef MAME_VIDEO_POLY_H
#define MAME_VIDEO_POLY_H
#pragma once
#include "screen.h"
#include <limits.h>
#include <atomic>
//**************************************************************************
// DEBUGGING
//**************************************************************************
// keep statistics
#define KEEP_POLY_STATISTICS 0
//**************************************************************************
// TYPE DEFINITIONS
//**************************************************************************
// poly_manager is a template class
template<typename _BaseType, class _ObjectData, int _MaxParams, int _MaxPolys>
class poly_manager
{
public:
static constexpr uint8_t FLAG_INCLUDE_BOTTOM_EDGE = 0x01;
static constexpr uint8_t FLAG_INCLUDE_RIGHT_EDGE = 0x02;
static constexpr uint8_t FLAG_NO_WORK_QUEUE = 0x04;
// each vertex has an X/Y coordinate and a set of parameters
struct vertex_t
{
vertex_t() { }
vertex_t(_BaseType _x, _BaseType _y) { x = _x; y = _y; }
_BaseType x, y; // X, Y coordinates
_BaseType p[_MaxParams]; // interpolated parameters
};
// a single extent describes a span and a list of parameter extents
struct extent_t
{
int16_t startx, stopx; // starting (inclusive)/ending (exclusive) endpoints
struct
{
_BaseType start; // parameter value at start
_BaseType dpdx; // dp/dx relative to start
} param[_MaxParams];
void *userdata; // custom per-span data
};
// delegate type for scanline callbacks
typedef delegate<void (int32_t, const extent_t &, const _ObjectData &, int)> render_delegate;
// construction/destruction
poly_manager(running_machine &machine, uint8_t flags = 0);
poly_manager(screen_device &screen, uint8_t flags = 0);
virtual ~poly_manager();
// getters
running_machine &machine() const { return m_machine; }
screen_device &screen() const { assert(m_screen != nullptr); return *m_screen; }
uint32_t triangles_drawn() const { return m_triangles; }
// synchronization
void wait(const char *debug_reason = "general");
// object data allocators
_ObjectData &object_data_alloc();
_ObjectData &object_data_last() const { return m_object.last(); }
// tiles
uint32_t render_tile(const rectangle &cliprect, render_delegate callback, int paramcount, const vertex_t &v1, const vertex_t &v2);
// triangles
uint32_t render_triangle(const rectangle &cliprect, render_delegate callback, int paramcount, const vertex_t &v1, const vertex_t &v2, const vertex_t &v3);
uint32_t render_triangle_fan(const rectangle &cliprect, render_delegate callback, int paramcount, int numverts, const vertex_t *v);
uint32_t render_triangle_strip(const rectangle &cliprect, render_delegate callback, int paramcount, int numverts, const vertex_t *v);
uint32_t render_triangle_custom(const rectangle &cliprect, render_delegate callback, int startscanline, int numscanlines, const extent_t *extents);
// polygons
template<int _NumVerts>
uint32_t render_polygon(const rectangle &cliprect, render_delegate callback, int paramcount, const vertex_t *v);
// public helpers
int zclip_if_less(int numverts, const vertex_t *v, vertex_t *outv, int paramcount, _BaseType clipval);
private:
poly_manager(running_machine &machine, screen_device *screen, uint8_t flags);
// turn this on to log the reasons for any long waits
static constexpr bool POLY_LOG_WAITS = false;
// number of profiling ticks before we consider a wait "long"
static constexpr osd_ticks_t POLY_LOG_WAIT_THRESHOLD = 1000;
static constexpr int SCANLINES_PER_BUCKET = 32;
static constexpr int CACHE_LINE_SIZE = 64; // this is a general guess
static constexpr int TOTAL_BUCKETS = (512 / SCANLINES_PER_BUCKET);
static constexpr int UNITS_PER_POLY = (100 / SCANLINES_PER_BUCKET);
// polygon_info describes a single polygon, which includes the poly_params
struct polygon_info
{
poly_manager * m_owner; // pointer back to the poly manager
_ObjectData * m_object; // object data pointer
render_delegate m_callback; // callback to handle a scanline's worth of work
};
// internal unit of work
struct work_unit
{
std::atomic<uint32_t> count_next; // number of scanlines and index of next item to process
polygon_info * polygon; // pointer to polygon
int16_t scanline; // starting scanline
uint16_t previtem; // index of previous item in the same bucket
#ifndef PTR64
uint32_t dummy; // pad to 16 bytes
#endif
extent_t extent[SCANLINES_PER_BUCKET]; // array of scanline extents
};
//-------------------------------------------------
// global helpers for float base types
//-------------------------------------------------
static float poly_floor(float x) { return floorf(x); }
static float poly_abs(float x) { return fabsf(x); }
static float poly_recip(float x) { return 1.0f / x; }
//-------------------------------------------------
// global helpers for double base types
//-------------------------------------------------
static double poly_floor(double x) { return floor(x); }
static double poly_abs(double x) { return fabs(x); }
static double poly_recip(double x) { return 1.0 / x; }
// class for managing an array of items
template<class _Type, int _Count>
class poly_array
{
// size of an item, rounded up to the cache line size
static const int k_itemsize = ((sizeof(_Type) + CACHE_LINE_SIZE - 1) / CACHE_LINE_SIZE) * CACHE_LINE_SIZE;
public:
// construction
poly_array(running_machine &machine, poly_manager &manager)
: m_manager(manager),
m_base(make_unique_clear<uint8_t[]>(k_itemsize * _Count)),
m_next(0),
m_max(0),
m_waits(0) { }
// destruction
~poly_array() { m_base = nullptr; }
// operators
_Type &operator[](int index) const { assert(index >= 0 && index < _Count); return *reinterpret_cast<_Type *>(m_base.get() + index * k_itemsize); }
// getters
int count() const { return m_next; }
int max() const { return m_max; }
int waits() const { return m_waits; }
int itemsize() const { return k_itemsize; }
int allocated() const { return _Count; }
int indexof(_Type &item) const { int result = (reinterpret_cast<uint8_t *>(&item) - m_base.get()) / k_itemsize; assert(result >= 0 && result < _Count); return result; }
// operations
void reset() { m_next = 0; }
_Type &next() { if (m_next > m_max) m_max = m_next; assert(m_next < _Count); return *new(m_base.get() + m_next++ * k_itemsize) _Type; }
_Type &last() const { return (*this)[m_next - 1]; }
void wait_for_space(int count = 1) { while ((m_next + count) >= _Count) { m_waits++; m_manager.wait(""); } }
private:
// internal state
poly_manager & m_manager;
std::unique_ptr<uint8_t[]> m_base;
int m_next;
int m_max;
int m_waits;
};
// internal array types
typedef poly_array<polygon_info, _MaxPolys> polygon_array;
typedef poly_array<_ObjectData, _MaxPolys + 1> objectdata_array;
typedef poly_array<work_unit, std::min(_MaxPolys * UNITS_PER_POLY, 65535)> unit_array;
// round in a cross-platform consistent manner
inline int32_t round_coordinate(_BaseType value)
{
int32_t result = poly_floor(value);
if ((value > 0) && (result < 0))
return INT_MAX-1;
return result + (value - _BaseType(result) > _BaseType(0.5));
}
// internal helpers
polygon_info &polygon_alloc(int minx, int maxx, int miny, int maxy, render_delegate callback)
{
// wait for space in the polygon and unit arrays
m_polygon.wait_for_space();
m_unit.wait_for_space((maxy - miny) / SCANLINES_PER_BUCKET + 2);
// return and initialize the next one
polygon_info &polygon = m_polygon.next();
polygon.m_owner = this;
polygon.m_object = &object_data_last();
polygon.m_callback = callback;
return polygon;
}
static void *work_item_callback(void *param, int threadid);
void presave() { wait("pre-save"); }
// queue management
running_machine & m_machine;
screen_device * m_screen;
osd_work_queue * m_queue; // work queue
// arrays
polygon_array m_polygon; // array of polygons
objectdata_array m_object; // array of object data
unit_array m_unit; // array of work units
// misc data
uint8_t const m_flags; // flags
// buckets
uint16_t m_unit_bucket[TOTAL_BUCKETS]; // buckets for tracking unit usage
// statistics
uint32_t m_tiles; // number of tiles queued
uint32_t m_triangles; // number of triangles queued
uint32_t m_quads; // number of quads queued
uint64_t m_pixels; // number of pixels rendered
#if KEEP_POLY_STATISTICS
uint32_t m_conflicts[WORK_MAX_THREADS]; // number of conflicts found, per thread
uint32_t m_resolved[WORK_MAX_THREADS]; // number of conflicts resolved, per thread
#endif
};
//-------------------------------------------------
// poly_manager - constructor
//-------------------------------------------------
template<typename _BaseType, class _ObjectData, int _MaxParams, int _MaxPolys>
poly_manager<_BaseType, _ObjectData, _MaxParams, _MaxPolys>::poly_manager(running_machine &machine, uint8_t flags)
: poly_manager(machine, nullptr, flags)
{
}
template<typename _BaseType, class _ObjectData, int _MaxParams, int _MaxPolys>
poly_manager<_BaseType, _ObjectData, _MaxParams, _MaxPolys>::poly_manager(screen_device &screen, uint8_t flags)
: poly_manager(screen.machine(), &screen, flags)
{
}
template<typename _BaseType, class _ObjectData, int _MaxParams, int _MaxPolys>
poly_manager<_BaseType, _ObjectData, _MaxParams, _MaxPolys>::poly_manager(running_machine &machine, screen_device *screen, uint8_t flags)
: m_machine(machine)
, m_screen(screen)
, m_queue(nullptr)
, m_polygon(machine, *this)
, m_object(machine, *this)
, m_unit(machine, *this)
, m_flags(flags)
, m_tiles(0)
, m_triangles(0)
, m_quads(0)
, m_pixels(0)
{
#if KEEP_POLY_STATISTICS
memset(m_conflicts, 0, sizeof(m_conflicts));
memset(m_resolved, 0, sizeof(m_resolved));
#endif
// create the work queue
if (!(flags & FLAG_NO_WORK_QUEUE))
m_queue = osd_work_queue_alloc(WORK_QUEUE_FLAG_MULTI | WORK_QUEUE_FLAG_HIGH_FREQ);
memset(m_unit_bucket, 0xff, sizeof(m_unit_bucket));
// request a pre-save callback for synchronization
machine.save().register_presave(save_prepost_delegate(FUNC(poly_manager::presave), this));
}
//-------------------------------------------------
// ~poly_manager - destructor
//-------------------------------------------------
template<typename _BaseType, class _ObjectData, int _MaxParams, int _MaxPolys>
poly_manager<_BaseType, _ObjectData, _MaxParams, _MaxPolys>::~poly_manager()
{
#if KEEP_POLY_STATISTICS
{
// accumulate stats over the entire collection
int conflicts = 0, resolved = 0;
for (int i = 0; i < ARRAY_LENGTH(m_conflicts); i++)
{
conflicts += m_conflicts[i];
resolved += m_resolved[i];
}
// output global stats
printf("Total triangles = %d\n", m_triangles);
printf("Total quads = %d\n", m_quads);
if (m_pixels > 1000000000)
printf("Total pixels = %d%09d\n", (uint32_t)(m_pixels / 1000000000), (uint32_t)(m_pixels % 1000000000));
else
printf("Total pixels = %d\n", (uint32_t)m_pixels);
printf("Conflicts: %d resolved, %d total\n", resolved, conflicts);
printf("Units: %5d used, %5d allocated, %5d waits, %4d bytes each, %7d total\n", m_unit.max(), m_unit.allocated(), m_unit.waits(), m_unit.itemsize(), m_unit.allocated() * m_unit.itemsize());
printf("Polygons: %5d used, %5d allocated, %5d waits, %4d bytes each, %7d total\n", m_polygon.max(), m_polygon.allocated(), m_polygon.waits(), m_polygon.itemsize(), m_polygon.allocated() * m_polygon.itemsize());
printf("Object data: %5d used, %5d allocated, %5d waits, %4d bytes each, %7d total\n", m_object.max(), m_object.allocated(), m_object.waits(), m_object.itemsize(), m_object.allocated() * m_object.itemsize());
}
#endif
// free the work queue
if (m_queue != nullptr)
osd_work_queue_free(m_queue);
}
//-------------------------------------------------
// work_item_callback - process a work item
//-------------------------------------------------
template<typename _BaseType, class _ObjectData, int _MaxParams, int _MaxPolys>
void *poly_manager<_BaseType, _ObjectData, _MaxParams, _MaxPolys>::work_item_callback(void *param, int threadid)
{
while (1)
{
work_unit &unit = *(work_unit *)param;
polygon_info &polygon = *unit.polygon;
int count = unit.count_next & 0xffff;
uint32_t orig_count_next;
// if our previous item isn't done yet, enqueue this item to the end and proceed
if (unit.previtem != 0xffff)
{
work_unit &prevunit = polygon.m_owner->m_unit[unit.previtem];
if (prevunit.count_next != 0)
{
uint32_t unitnum = polygon.m_owner->m_unit.indexof(unit);
uint32_t new_count_next;
// attempt to atomically swap in this new value
do
{
orig_count_next = prevunit.count_next;
new_count_next = orig_count_next | (unitnum << 16);
} while (!prevunit.count_next.compare_exchange_weak(orig_count_next, new_count_next, std::memory_order_release, std::memory_order_relaxed));
#if KEEP_POLY_STATISTICS
// track resolved conflicts
polygon.m_owner->m_conflicts[threadid]++;
if (orig_count_next != 0)
polygon.m_owner->m_resolved[threadid]++;
#endif
// if we succeeded, skip out early so we can do other work
if (orig_count_next != 0)
break;
}
}
// iterate over extents
for (int curscan = 0; curscan < count; curscan++)
polygon.m_callback(unit.scanline + curscan, unit.extent[curscan], *polygon.m_object, threadid);
// set our count to 0 and re-fetch the original count value
do
{
orig_count_next = unit.count_next;
} while (!unit.count_next.compare_exchange_weak(orig_count_next, 0, std::memory_order_release, std::memory_order_relaxed));
// if we have no more work to do, do nothing
orig_count_next >>= 16;
if (orig_count_next == 0)
break;
param = &polygon.m_owner->m_unit[orig_count_next];
}
return nullptr;
}
//-------------------------------------------------
// wait - stall until all work is complete
//-------------------------------------------------
template<typename _BaseType, class _ObjectData, int _MaxParams, int _MaxPolys>
void poly_manager<_BaseType, _ObjectData, _MaxParams, _MaxPolys>::wait(const char *debug_reason)
{
osd_ticks_t time;
// remember the start time if we're logging
if (POLY_LOG_WAITS)
time = get_profile_ticks();
// wait for all pending work items to complete
if (m_queue != nullptr)
osd_work_queue_wait(m_queue, osd_ticks_per_second() * 100);
// if we don't have a queue, just run the whole list now
else
for (int unitnum = 0; unitnum < m_unit.count(); unitnum++)
work_item_callback(&m_unit[unitnum], 0);
// log any long waits
if (POLY_LOG_WAITS)
{
time = get_profile_ticks() - time;
if (time > POLY_LOG_WAIT_THRESHOLD)
machine().logerror("Poly:Waited %d cycles for %s\n", (int)time, debug_reason);
}
// reset the state
m_polygon.reset();
m_unit.reset();
memset(m_unit_bucket, 0xff, sizeof(m_unit_bucket));
// we need to preserve the last object data that was supplied
if (m_object.count() > 0)
{
_ObjectData temp = object_data_last();
m_object.reset();
m_object.next() = temp;
}
else
m_object.reset();
}
//-------------------------------------------------
// object_data_alloc - allocate a new _ObjectData
//-------------------------------------------------
template<typename _BaseType, class _ObjectData, int _MaxParams, int _MaxPolys>
_ObjectData &poly_manager<_BaseType, _ObjectData, _MaxParams, _MaxPolys>::object_data_alloc()
{
// wait for a work item if we have to, then return the next item
m_object.wait_for_space();
return m_object.next();
}
//-------------------------------------------------
// render_tile - render a tile
//-------------------------------------------------
template<typename _BaseType, class _ObjectData, int _MaxParams, int _MaxPolys>
uint32_t poly_manager<_BaseType, _ObjectData, _MaxParams, _MaxPolys>::render_tile(const rectangle &cliprect, render_delegate callback, int paramcount, const vertex_t &_v1, const vertex_t &_v2)
{
const vertex_t *v1 = &_v1;
const vertex_t *v2 = &_v2;
// first sort by Y
if (v2->y < v1->y)
{
const vertex_t *tv = v1;
v1 = v2;
v2 = tv;
}
// compute some integral X/Y vertex values
int32_t v1y = round_coordinate(v1->y);
int32_t v2y = round_coordinate(v2->y);
// clip coordinates
int32_t v1yclip = v1y;
int32_t v2yclip = v2y + ((m_flags & FLAG_INCLUDE_BOTTOM_EDGE) ? 1 : 0);
v1yclip = std::max(v1yclip, cliprect.top());
v2yclip = std::min(v2yclip, cliprect.bottom() + 1);
if (v2yclip - v1yclip <= 0)
return 0;
// determine total X extents
_BaseType minx = v1->x;
_BaseType maxx = v2->x;
if (minx > maxx)
return 0;
// allocate and populate a new polygon
polygon_info &polygon = polygon_alloc(round_coordinate(minx), round_coordinate(maxx), v1yclip, v2yclip, callback);
// compute parameter deltas
_BaseType param_dpdx[_MaxParams];
_BaseType param_dpdy[_MaxParams];
if (paramcount > 0)
{
_BaseType oox = poly_recip(v2->x - v1->x);
_BaseType ooy = poly_recip(v2->y - v1->y);
for (int paramnum = 0; paramnum < paramcount; paramnum++)
{
param_dpdx[paramnum] = oox * (v2->p[paramnum] - v1->p[paramnum]);
param_dpdy[paramnum] = ooy * (v2->p[paramnum] - v1->p[paramnum]);
}
}
// clamp to full pixels
int32_t istartx = round_coordinate(v1->x);
int32_t istopx = round_coordinate(v2->x);
// force start < stop
if (istartx > istopx)
{
int32_t temp = istartx;
istartx = istopx;
istopx = temp;
}
// include the right edge if requested
if (m_flags & FLAG_INCLUDE_RIGHT_EDGE)
istopx++;
// apply left/right clipping
if (istartx < cliprect.left())
istartx = cliprect.left();
if (istopx > cliprect.right())
istopx = cliprect.right() + 1;
if (istartx >= istopx)
return 0;
// compute the X extents for each scanline
int32_t pixels = 0;
uint32_t startunit = m_unit.count();
int32_t scaninc = 1;
for (int32_t curscan = v1yclip; curscan < v2yclip; curscan += scaninc)
{
uint32_t bucketnum = ((uint32_t)curscan / SCANLINES_PER_BUCKET) % TOTAL_BUCKETS;
uint32_t unit_index = m_unit.count();
work_unit &unit = m_unit.next();
// determine how much to advance to hit the next bucket
scaninc = SCANLINES_PER_BUCKET - (uint32_t)curscan % SCANLINES_PER_BUCKET;
// fill in the work unit basics
unit.polygon = &polygon;
unit.count_next = std::min(v2yclip - curscan, scaninc);
unit.scanline = curscan;
unit.previtem = m_unit_bucket[bucketnum];
m_unit_bucket[bucketnum] = unit_index;
// iterate over extents
for (int extnum = 0; extnum < unit.count_next; extnum++)
{
// compute the ending X based on which part of the triangle we're in
_BaseType fully = _BaseType(curscan + extnum) + _BaseType(0.5);
// set the extent and update the total pixel count
extent_t &extent = unit.extent[extnum];
extent.startx = istartx;
extent.stopx = istopx;
extent.userdata = nullptr;
pixels += istopx - istartx;
// fill in the parameters for the extent
_BaseType fullstartx = _BaseType(istartx) + _BaseType(0.5);
for (int paramnum = 0; paramnum < paramcount; paramnum++)
{
extent.param[paramnum].start = v1->p[paramnum] + fullstartx * param_dpdx[paramnum] + fully * param_dpdy[paramnum];
extent.param[paramnum].dpdx = param_dpdx[paramnum];
}
}
}
// enqueue the work items
if (m_queue != nullptr)
osd_work_item_queue_multiple(m_queue, work_item_callback, m_unit.count() - startunit, &m_unit[startunit], m_unit.itemsize(), WORK_ITEM_FLAG_AUTO_RELEASE);
// return the total number of pixels in the triangle
m_tiles++;
m_pixels += pixels;
return pixels;
}
//-------------------------------------------------
// render_triangle - render a single triangle
// given 3 vertexes
//-------------------------------------------------
template<typename _BaseType, class _ObjectData, int _MaxParams, int _MaxPolys>
uint32_t poly_manager<_BaseType, _ObjectData, _MaxParams, _MaxPolys>::render_triangle(const rectangle &cliprect, render_delegate callback, int paramcount, const vertex_t &_v1, const vertex_t &_v2, const vertex_t &_v3)
{
const vertex_t *v1 = &_v1;
const vertex_t *v2 = &_v2;
const vertex_t *v3 = &_v3;
// first sort by Y
if (v2->y < v1->y)
{
const vertex_t *tv = v1;
v1 = v2;
v2 = tv;
}
if (v3->y < v2->y)
{
const vertex_t *tv = v2;
v2 = v3;
v3 = tv;
if (v2->y < v1->y)
{
const vertex_t *tv2 = v1;
v1 = v2;
v2 = tv2;
}
}
// compute some integral X/Y vertex values
int32_t v1y = round_coordinate(v1->y);
int32_t v3y = round_coordinate(v3->y);
// clip coordinates
int32_t v1yclip = v1y;
int32_t v3yclip = v3y + ((m_flags & FLAG_INCLUDE_BOTTOM_EDGE) ? 1 : 0);
v1yclip = std::max(v1yclip, cliprect.top());
v3yclip = std::min(v3yclip, cliprect.bottom() + 1);
if (v3yclip - v1yclip <= 0)
return 0;
// determine total X extents
_BaseType minx = v1->x;
_BaseType maxx = v1->x;
if (v2->x < minx) minx = v2->x;
else if (v2->x > maxx) maxx = v2->x;
if (v3->x < minx) minx = v3->x;
else if (v3->x > maxx) maxx = v3->x;
// allocate and populate a new polygon
polygon_info &polygon = polygon_alloc(round_coordinate(minx), round_coordinate(maxx), v1yclip, v3yclip, callback);
// compute the slopes for each portion of the triangle
_BaseType dxdy_v1v2 = (v2->y == v1->y) ? _BaseType(0.0) : (v2->x - v1->x) / (v2->y - v1->y);
_BaseType dxdy_v1v3 = (v3->y == v1->y) ? _BaseType(0.0) : (v3->x - v1->x) / (v3->y - v1->y);
_BaseType dxdy_v2v3 = (v3->y == v2->y) ? _BaseType(0.0) : (v3->x - v2->x) / (v3->y - v2->y);
// compute parameter starting points and deltas
_BaseType param_start[_MaxParams];
_BaseType param_dpdx[_MaxParams];
_BaseType param_dpdy[_MaxParams];
if (paramcount > 0)
{
_BaseType a00 = v2->y - v3->y;
_BaseType a01 = v3->x - v2->x;
_BaseType a02 = v2->x*v3->y - v3->x*v2->y;
_BaseType a10 = v3->y - v1->y;
_BaseType a11 = v1->x - v3->x;
_BaseType a12 = v3->x*v1->y - v1->x*v3->y;
_BaseType a20 = v1->y - v2->y;
_BaseType a21 = v2->x - v1->x;
_BaseType a22 = v1->x*v2->y - v2->x*v1->y;
_BaseType det = a02 + a12 + a22;
if (poly_abs(det) < _BaseType(0.00001))
{
for (int paramnum = 0; paramnum < paramcount; paramnum++)
{
param_dpdx[paramnum] = _BaseType(0.0);
param_dpdy[paramnum] = _BaseType(0.0);
param_start[paramnum] = v1->p[paramnum];
}
}
else
{
_BaseType idet = poly_recip(det);
for (int paramnum = 0; paramnum < paramcount; paramnum++)
{
param_dpdx[paramnum] = idet * (v1->p[paramnum]*a00 + v2->p[paramnum]*a10 + v3->p[paramnum]*a20);
param_dpdy[paramnum] = idet * (v1->p[paramnum]*a01 + v2->p[paramnum]*a11 + v3->p[paramnum]*a21);
param_start[paramnum] = idet * (v1->p[paramnum]*a02 + v2->p[paramnum]*a12 + v3->p[paramnum]*a22);
}
}
}
else // GCC 4.7.0 incorrectly claims these are uninitialized; humor it by initializing in the (hopefully rare) zero parameter case
{
param_start[0] = _BaseType(0.0);
param_dpdx[0] = _BaseType(0.0);
param_dpdy[0] = _BaseType(0.0);
}
// compute the X extents for each scanline
int32_t pixels = 0;
uint32_t startunit = m_unit.count();
int32_t scaninc = 1;
for (int32_t curscan = v1yclip; curscan < v3yclip; curscan += scaninc)
{
uint32_t bucketnum = ((uint32_t)curscan / SCANLINES_PER_BUCKET) % TOTAL_BUCKETS;
uint32_t unit_index = m_unit.count();
work_unit &unit = m_unit.next();
// determine how much to advance to hit the next bucket
scaninc = SCANLINES_PER_BUCKET - (uint32_t)curscan % SCANLINES_PER_BUCKET;
// fill in the work unit basics
unit.polygon = &polygon;
unit.count_next = std::min(v3yclip - curscan, scaninc);
unit.scanline = curscan;
unit.previtem = m_unit_bucket[bucketnum];
m_unit_bucket[bucketnum] = unit_index;
// iterate over extents
for (int extnum = 0; extnum < unit.count_next; extnum++)
{
// compute the ending X based on which part of the triangle we're in
_BaseType fully = _BaseType(curscan + extnum) + _BaseType(0.5);
_BaseType startx = v1->x + (fully - v1->y) * dxdy_v1v3;
_BaseType stopx;
if (fully < v2->y)
stopx = v1->x + (fully - v1->y) * dxdy_v1v2;
else
stopx = v2->x + (fully - v2->y) * dxdy_v2v3;
// clamp to full pixels
int32_t istartx = round_coordinate(startx);
int32_t istopx = round_coordinate(stopx);
// force start < stop
if (istartx > istopx)
{
int32_t temp = istartx;
istartx = istopx;
istopx = temp;
}
// include the right edge if requested
if (m_flags & FLAG_INCLUDE_RIGHT_EDGE)
istopx++;
// apply left/right clipping
if (istartx < cliprect.left())
istartx = cliprect.left();
if (istopx > cliprect.right())
istopx = cliprect.right() + 1;
// set the extent and update the total pixel count
if (istartx >= istopx)
istartx = istopx = 0;
extent_t &extent = unit.extent[extnum];
extent.startx = istartx;
extent.stopx = istopx;
extent.userdata = nullptr;
pixels += istopx - istartx;
// fill in the parameters for the extent
_BaseType fullstartx = _BaseType(istartx) + _BaseType(0.5);
for (int paramnum = 0; paramnum < paramcount; paramnum++)
{
extent.param[paramnum].start = param_start[paramnum] + fullstartx * param_dpdx[paramnum] + fully * param_dpdy[paramnum];
extent.param[paramnum].dpdx = param_dpdx[paramnum];
}
}
}
// enqueue the work items
if (m_queue != nullptr)
osd_work_item_queue_multiple(m_queue, work_item_callback, m_unit.count() - startunit, &m_unit[startunit], m_unit.itemsize(), WORK_ITEM_FLAG_AUTO_RELEASE);
// return the total number of pixels in the triangle
m_triangles++;
m_pixels += pixels;
return pixels;
}
//-------------------------------------------------
// render_triangle_fan - render a set of
// triangles in a fan
//-------------------------------------------------
template<typename _BaseType, class _ObjectData, int _MaxParams, int _MaxPolys>
uint32_t poly_manager<_BaseType, _ObjectData, _MaxParams, _MaxPolys>::render_triangle_fan(const rectangle &cliprect, render_delegate callback, int paramcount, int numverts, const vertex_t *v)
{
// iterate over vertices
uint32_t pixels = 0;
for (int vertnum = 2; vertnum < numverts; vertnum++)
pixels += render_triangle(cliprect, callback, paramcount, v[0], v[vertnum - 1], v[vertnum]);
return pixels;
}
//-------------------------------------------------
// render_triangle_strip - render a set of
// triangles in a strip
//-------------------------------------------------
template<typename _BaseType, class _ObjectData, int _MaxParams, int _MaxPolys>
uint32_t poly_manager<_BaseType, _ObjectData, _MaxParams, _MaxPolys>::render_triangle_strip(const rectangle &cliprect, render_delegate callback, int paramcount, int numverts, const vertex_t *v)
{
// iterate over vertices
uint32_t pixels = 0;
for (int vertnum = 2; vertnum < numverts; vertnum++)
pixels += render_triangle(cliprect, callback, paramcount, v[vertnum - 2], v[vertnum - 1], v[vertnum]);
return pixels;
}
//-------------------------------------------------
// render_triangle_custom - perform a custom
// render of an object, given specific extents
//-------------------------------------------------
template<typename _BaseType, class _ObjectData, int _MaxParams, int _MaxPolys>
uint32_t poly_manager<_BaseType, _ObjectData, _MaxParams, _MaxPolys>::render_triangle_custom(const rectangle &cliprect, render_delegate callback, int startscanline, int numscanlines, const extent_t *extents)
{
// clip coordinates
int32_t v1yclip = std::max(startscanline, cliprect.top());
int32_t v3yclip = std::min(startscanline + numscanlines, cliprect.bottom() + 1);
if (v3yclip - v1yclip <= 0)
return 0;
// allocate and populate a new polygon
polygon_info &polygon = polygon_alloc(0, 0, v1yclip, v3yclip, callback);
// compute the X extents for each scanline
int32_t pixels = 0;
uint32_t startunit = m_unit.count();
int32_t scaninc = 1;
for (int32_t curscan = v1yclip; curscan < v3yclip; curscan += scaninc)
{
uint32_t bucketnum = ((uint32_t)curscan / SCANLINES_PER_BUCKET) % TOTAL_BUCKETS;
uint32_t unit_index = m_unit.count();
work_unit &unit = m_unit.next();
// determine how much to advance to hit the next bucket
scaninc = SCANLINES_PER_BUCKET - (uint32_t)curscan % SCANLINES_PER_BUCKET;
// fill in the work unit basics
unit.polygon = &polygon;
unit.count_next = std::min(v3yclip - curscan, scaninc);
unit.scanline = curscan;
unit.previtem = m_unit_bucket[bucketnum];
m_unit_bucket[bucketnum] = unit_index;
// iterate over extents
for (int extnum = 0; extnum < unit.count_next; extnum++)
{
const extent_t &srcextent = extents[(curscan + extnum) - startscanline];
int32_t istartx = srcextent.startx, istopx = srcextent.stopx;
// apply left/right clipping
if (istartx < cliprect.left())
istartx = cliprect.left();
if (istartx > cliprect.right())
istartx = cliprect.right() + 1;
if (istopx < cliprect.left())
istopx = cliprect.left();
if (istopx > cliprect.right())
istopx = cliprect.right() + 1;
// set the extent and update the total pixel count
extent_t &extent = unit.extent[extnum];
extent.startx = istartx;
extent.stopx = istopx;
// fill in the parameters for the extent
for (int paramnum = 0; paramnum < _MaxParams; paramnum++)
{
extent.param[paramnum].start = srcextent.param[paramnum].start;
extent.param[paramnum].dpdx = srcextent.param[paramnum].dpdx;
}
extent.userdata = srcextent.userdata;
if (istartx < istopx)
pixels += istopx - istartx;
else if(istopx < istartx)
pixels += istartx - istopx;
}
}
// enqueue the work items
if (m_queue != nullptr)
osd_work_item_queue_multiple(m_queue, work_item_callback, m_unit.count() - startunit, &m_unit[startunit], m_unit.itemsize(), WORK_ITEM_FLAG_AUTO_RELEASE);
// return the total number of pixels in the object
m_triangles++;
m_pixels += pixels;
return pixels;
}
//-------------------------------------------------
// render_polygon - render a single polygon up
// to 32 vertices
//-------------------------------------------------
template<typename _BaseType, class _ObjectData, int _MaxParams, int _MaxPolys>
template<int _NumVerts>
uint32_t poly_manager<_BaseType, _ObjectData, _MaxParams, _MaxPolys>::render_polygon(const rectangle &cliprect, render_delegate callback, int paramcount, const vertex_t *v)
{
// determine min/max Y vertices
_BaseType minx = v[0].x;
_BaseType maxx = v[0].x;
int minv = 0;
int maxv = 0;
for (int vertnum = 1; vertnum < _NumVerts; vertnum++)
{
if (v[vertnum].y < v[minv].y)
minv = vertnum;
else if (v[vertnum].y > v[maxv].y)
maxv = vertnum;
if (v[vertnum].x < minx)
minx = v[vertnum].x;
else if (v[vertnum].x > maxx)
maxx = v[vertnum].x;
}
// determine start/end scanlines
int32_t miny = round_coordinate(v[minv].y);
int32_t maxy = round_coordinate(v[maxv].y);
// clip coordinates
int32_t minyclip = miny;
int32_t maxyclip = maxy + ((m_flags & FLAG_INCLUDE_BOTTOM_EDGE) ? 1 : 0);
minyclip = std::max(minyclip, cliprect.top());
maxyclip = std::min(maxyclip, cliprect.bottom() + 1);
if (maxyclip - minyclip <= 0)
return 0;
// allocate a new polygon
polygon_info &polygon = polygon_alloc(round_coordinate(minx), round_coordinate(maxx), minyclip, maxyclip, callback);
// walk forward to build up the forward edge list
struct poly_edge
{
poly_edge * next; // next edge in sequence
int index; // index of this edge
const vertex_t * v1; // pointer to first vertex
const vertex_t * v2; // pointer to second vertex
_BaseType dxdy; // dx/dy along the edge
_BaseType dpdy[_MaxParams]; // per-parameter dp/dy values
};
poly_edge fedgelist[_NumVerts - 1];
poly_edge *edgeptr = &fedgelist[0];
for (int curv = minv; curv != maxv; curv = (curv == _NumVerts - 1) ? 0 : (curv + 1))
{
// set the two vertices
edgeptr->v1 = &v[curv];
edgeptr->v2 = &v[(curv == _NumVerts - 1) ? 0 : (curv + 1)];
// if horizontal, skip altogether
if (edgeptr->v1->y == edgeptr->v2->y)
continue;
// need dx/dy always, and parameter deltas as necessary
_BaseType ooy = poly_recip(edgeptr->v2->y - edgeptr->v1->y);
edgeptr->dxdy = (edgeptr->v2->x - edgeptr->v1->x) * ooy;
for (int paramnum = 0; paramnum < paramcount; paramnum++)
edgeptr->dpdy[paramnum] = (edgeptr->v2->p[paramnum] - edgeptr->v1->p[paramnum]) * ooy;
++edgeptr;
}
// walk backward to build up the backward edge list
poly_edge bedgelist[_NumVerts - 1];
edgeptr = &bedgelist[0];
for (int curv = minv; curv != maxv; curv = (curv == 0) ? (_NumVerts - 1) : (curv - 1))
{
// set the two vertices
edgeptr->v1 = &v[curv];
edgeptr->v2 = &v[(curv == 0) ? (_NumVerts - 1) : (curv - 1)];
// if horizontal, skip altogether
if (edgeptr->v1->y == edgeptr->v2->y)
continue;
// need dx/dy always, and parameter deltas as necessary
_BaseType ooy = poly_recip(edgeptr->v2->y - edgeptr->v1->y);
edgeptr->dxdy = (edgeptr->v2->x - edgeptr->v1->x) * ooy;
for (int paramnum = 0; paramnum < paramcount; paramnum++)
edgeptr->dpdy[paramnum] = (edgeptr->v2->p[paramnum] - edgeptr->v1->p[paramnum]) * ooy;
++edgeptr;
}
// determine which list is left/right:
// if the first vertex is shared, compare the slopes
// if the first vertex is not shared, compare the X coordinates
const poly_edge *ledge, *redge;
if ((fedgelist[0].v1 == bedgelist[0].v1 && fedgelist[0].dxdy < bedgelist[0].dxdy) ||
(fedgelist[0].v1 != bedgelist[0].v1 && fedgelist[0].v1->x < bedgelist[0].v1->x))
{
ledge = fedgelist;
redge = bedgelist;
}
else
{
ledge = bedgelist;
redge = fedgelist;
}
// compute the X extents for each scanline
int32_t pixels = 0;
uint32_t startunit = m_unit.count();
int32_t scaninc = 1;
for (int32_t curscan = minyclip; curscan < maxyclip; curscan += scaninc)
{
uint32_t bucketnum = ((uint32_t)curscan / SCANLINES_PER_BUCKET) % TOTAL_BUCKETS;
uint32_t unit_index = m_unit.count();
work_unit &unit = m_unit.next();
// determine how much to advance to hit the next bucket
scaninc = SCANLINES_PER_BUCKET - (uint32_t)curscan % SCANLINES_PER_BUCKET;
// fill in the work unit basics
unit.polygon = &polygon;
unit.count_next = std::min(maxyclip - curscan, scaninc);
unit.scanline = curscan;
unit.previtem = m_unit_bucket[bucketnum];
m_unit_bucket[bucketnum] = unit_index;
// iterate over extents
for (int extnum = 0; extnum < unit.count_next; extnum++)
{
// compute the ending X based on which part of the triangle we're in
_BaseType fully = _BaseType(curscan + extnum) + _BaseType(0.5);
while (fully > ledge->v2->y && fully < v[maxv].y)
++ledge;
while (fully > redge->v2->y && fully < v[maxv].y)
++redge;
_BaseType startx = ledge->v1->x + (fully - ledge->v1->y) * ledge->dxdy;
_BaseType stopx = redge->v1->x + (fully - redge->v1->y) * redge->dxdy;
// clamp to full pixels
int32_t istartx = round_coordinate(startx);
int32_t istopx = round_coordinate(stopx);
// compute parameter starting points and deltas
extent_t &extent = unit.extent[extnum];
if (paramcount > 0)
{
_BaseType ldy = fully - ledge->v1->y;
_BaseType rdy = fully - redge->v1->y;
_BaseType oox = poly_recip(stopx - startx);
// iterate over parameters
for (int paramnum = 0; paramnum < paramcount; paramnum++)
{
_BaseType lparam = ledge->v1->p[paramnum] + ldy * ledge->dpdy[paramnum];
_BaseType rparam = redge->v1->p[paramnum] + rdy * redge->dpdy[paramnum];
_BaseType dpdx = (rparam - lparam) * oox;
extent.param[paramnum].start = lparam;// - (_BaseType(istartx) + 0.5f) * dpdx;
extent.param[paramnum].dpdx = dpdx;
}
}
// include the right edge if requested
if (m_flags & FLAG_INCLUDE_RIGHT_EDGE)
istopx++;
// apply left/right clipping
if (istartx < cliprect.left())
{
for (int paramnum = 0; paramnum < paramcount; paramnum++)
extent.param[paramnum].start += (cliprect.left() - istartx) * extent.param[paramnum].dpdx;
istartx = cliprect.left();
}
if (istopx > cliprect.right())
istopx = cliprect.right() + 1;
// set the extent and update the total pixel count
if (istartx >= istopx)
istartx = istopx = 0;
extent.startx = istartx;
extent.stopx = istopx;
extent.userdata = nullptr;
pixels += istopx - istartx;
}
}
// enqueue the work items
if (m_queue != nullptr)
osd_work_item_queue_multiple(m_queue, work_item_callback, m_unit.count() - startunit, &m_unit[startunit], m_unit.itemsize(), WORK_ITEM_FLAG_AUTO_RELEASE);
// return the total number of pixels in the triangle
m_quads++;
m_pixels += pixels;
return pixels;
}
//-------------------------------------------------
// zclip_if_less - clip a polygon using p[0] as
// a z coordinate
//-------------------------------------------------
template<typename _BaseType, class _ObjectData, int _MaxParams, int _MaxPolys>
int poly_manager<_BaseType, _ObjectData, _MaxParams, _MaxPolys>::zclip_if_less(int numverts, const vertex_t *v, vertex_t *outv, int paramcount, _BaseType clipval)
{
bool prevclipped = (v[numverts - 1].p[0] < clipval);
vertex_t *nextout = outv;
// iterate over vertices
for (int vertnum = 0; vertnum < numverts; vertnum++)
{
bool thisclipped = (v[vertnum].p[0] < clipval);
// if we switched from clipped to non-clipped, interpolate a vertex
if (thisclipped != prevclipped)
{
const vertex_t &v1 = v[(vertnum == 0) ? (numverts - 1) : (vertnum - 1)];
const vertex_t &v2 = v[vertnum];
_BaseType frac = (clipval - v1.p[0]) / (v2.p[0] - v1.p[0]);
nextout->x = v1.x + frac * (v2.x - v1.x);
nextout->y = v1.y + frac * (v2.y - v1.y);
for (int paramnum = 0; paramnum < paramcount; paramnum++)
nextout->p[paramnum] = v1.p[paramnum] + frac * (v2.p[paramnum] - v1.p[paramnum]);
++nextout;
}
// if this vertex is not clipped, copy it in
if (!thisclipped)
*nextout++ = v[vertnum];
// remember the last state
prevclipped = thisclipped;
}
return nextout - outv;
}
template<typename _BaseType, int _MaxParams>
struct frustum_clip_vertex
{
_BaseType x, y, z, w; // A 3d coordinate already transformed by a projection matrix
_BaseType p[_MaxParams]; // Additional parameters to clip
};
template<typename _BaseType, int _MaxParams>
int frustum_clip_w(const frustum_clip_vertex<_BaseType, _MaxParams>* v, int num_vertices, frustum_clip_vertex<_BaseType, _MaxParams>* out)
{
if (num_vertices <= 0)
return 0;
const _BaseType W_PLANE = 0.000001f;
frustum_clip_vertex<_BaseType, _MaxParams> clipv[10];
int clip_verts = 0;
int previ = num_vertices - 1;
for (int i=0; i < num_vertices; i++)
{
int v1_side = (v[i].w < W_PLANE) ? -1 : 1;
int v2_side = (v[previ].w < W_PLANE) ? -1 : 1;
if ((v1_side * v2_side) < 0) // edge goes through W plane
{
// insert vertex at intersection point
_BaseType wdiv = v[previ].w - v[i].w;
if (wdiv == 0.0f) // 0 edge means degenerate polygon
return 0;
_BaseType t = fabs((W_PLANE - v[previ].w) / wdiv);
clipv[clip_verts].x = v[previ].x + ((v[i].x - v[previ].x) * t);
clipv[clip_verts].y = v[previ].y + ((v[i].y - v[previ].y) * t);
clipv[clip_verts].z = v[previ].z + ((v[i].z - v[previ].z) * t);
clipv[clip_verts].w = v[previ].w + ((v[i].w - v[previ].w) * t);
// Interpolate the rest of the parameters
for (int pi = 0; pi < _MaxParams; pi++)
clipv[clip_verts].p[pi] = v[previ].p[pi] + ((v[i].p[pi] - v[previ].p[pi]) * t);
++clip_verts;
}
if (v1_side > 0) // current point is inside
{
clipv[clip_verts] = v[i];
++clip_verts;
}
previ = i;
}
memcpy(&out[0], &clipv[0], sizeof(out[0]) * clip_verts);
return clip_verts;
}
template<typename _BaseType, int _MaxParams>
int frustum_clip(const frustum_clip_vertex<_BaseType, _MaxParams>* v, int num_vertices, frustum_clip_vertex<_BaseType, _MaxParams>* out, int axis, int sign)
{
if (num_vertices <= 0)
return 0;
frustum_clip_vertex<_BaseType, _MaxParams> clipv[10];
int clip_verts = 0;
int previ = num_vertices - 1;
for (int i=0; i < num_vertices; i++)
{
int v1_side, v2_side;
_BaseType* v1a = (_BaseType*)&v[i];
_BaseType* v2a = (_BaseType*)&v[previ];
_BaseType v1_axis, v2_axis;
if (sign) // +axis
{
v1_axis = v1a[axis];
v2_axis = v2a[axis];
}
else // -axis
{
v1_axis = -v1a[axis];
v2_axis = -v2a[axis];
}
v1_side = (v1_axis <= v[i].w) ? 1 : -1;
v2_side = (v2_axis <= v[previ].w) ? 1 : -1;
if ((v1_side * v2_side) < 0) // edge goes through W plane
{
// insert vertex at intersection point
_BaseType wdiv = ((v[previ].w - v2_axis) - (v[i].w - v1_axis));
if (wdiv == 0.0f) // 0 edge means degenerate polygon
return 0;
_BaseType t = fabs((v[previ].w - v2_axis) / wdiv);
clipv[clip_verts].x = v[previ].x + ((v[i].x - v[previ].x) * t);
clipv[clip_verts].y = v[previ].y + ((v[i].y - v[previ].y) * t);
clipv[clip_verts].z = v[previ].z + ((v[i].z - v[previ].z) * t);
clipv[clip_verts].w = v[previ].w + ((v[i].w - v[previ].w) * t);
// Interpolate the rest of the parameters
for (int pi = 0; pi < _MaxParams; pi++)
clipv[clip_verts].p[pi] = v[previ].p[pi] + ((v[i].p[pi] - v[previ].p[pi]) * t);
++clip_verts;
}
if (v1_side > 0) // current point is inside
{
clipv[clip_verts] = v[i];
++clip_verts;
}
previ = i;
}
memcpy(&out[0], &clipv[0], sizeof(out[0]) * clip_verts);
return clip_verts;
}
template<typename _BaseType, int _MaxParams>
int frustum_clip_all(frustum_clip_vertex<_BaseType, _MaxParams>* clip_vert, int num_vertices, frustum_clip_vertex<_BaseType, _MaxParams>* out)
{
num_vertices = frustum_clip_w<_BaseType, _MaxParams>(clip_vert, num_vertices, clip_vert);
num_vertices = frustum_clip<_BaseType, _MaxParams>(clip_vert, num_vertices, clip_vert, 0, 0); // W <= -X
num_vertices = frustum_clip<_BaseType, _MaxParams>(clip_vert, num_vertices, clip_vert, 0, 1); // W <= +X
num_vertices = frustum_clip<_BaseType, _MaxParams>(clip_vert, num_vertices, clip_vert, 1, 0); // W <= -Y
num_vertices = frustum_clip<_BaseType, _MaxParams>(clip_vert, num_vertices, clip_vert, 1, 1); // W <= +X
num_vertices = frustum_clip<_BaseType, _MaxParams>(clip_vert, num_vertices, clip_vert, 2, 0); // W <= -Z
num_vertices = frustum_clip<_BaseType, _MaxParams>(clip_vert, num_vertices, clip_vert, 2, 1); // W <= +Z
out = clip_vert;
return num_vertices;
}
#endif // MAME_DEVICES_VIDEO_POLY_H