// 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 #include //************************************************************************** // DEBUGGING //************************************************************************** // keep statistics #define KEEP_POLY_STATISTICS 0 //************************************************************************** // TYPE DEFINITIONS //************************************************************************** // poly_manager is a template class template 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 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 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 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 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(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(&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 m_base; int m_next; int m_max; int m_waits; }; // internal array types typedef poly_array polygon_array; typedef poly_array<_ObjectData, _MaxPolys + 1> objectdata_array; typedef poly_array 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 poly_manager<_BaseType, _ObjectData, _MaxParams, _MaxPolys>::poly_manager(running_machine &machine, uint8_t flags) : poly_manager(machine, nullptr, flags) { } template poly_manager<_BaseType, _ObjectData, _MaxParams, _MaxPolys>::poly_manager(screen_device &screen, uint8_t flags) : poly_manager(screen.machine(), &screen, flags) { } template 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 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 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 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 _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 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 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 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 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 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 template 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 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 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 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 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 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