diff options
Diffstat (limited to 'trunk/src/emu/video/polynew.h')
-rw-r--r-- | trunk/src/emu/video/polynew.h | 1132 |
1 files changed, 1132 insertions, 0 deletions
diff --git a/trunk/src/emu/video/polynew.h b/trunk/src/emu/video/polynew.h new file mode 100644 index 00000000000..4b5fd553f13 --- /dev/null +++ b/trunk/src/emu/video/polynew.h @@ -0,0 +1,1132 @@ +/*************************************************************************** + + poly.h + + New 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) + +***************************************************************************/ + +#pragma once + +#ifndef __POLYNEW_H__ +#define __POLYNEW_H__ + + +//************************************************************************** +// DEBUGGING +//************************************************************************** + +// keep statistics +#define KEEP_STATISTICS 0 + +// turn this on to log the reasons for any long waits +#define LOG_WAITS 0 + +// number of profiling ticks before we consider a wait "long" +#define LOG_WAIT_THRESHOLD 1000 + + + +/*************************************************************************** + CONSTANTS +***************************************************************************/ + +#define POLYFLAG_INCLUDE_BOTTOM_EDGE 0x01 +#define POLYFLAG_INCLUDE_RIGHT_EDGE 0x02 +#define POLYFLAG_NO_WORK_QUEUE 0x04 + +#define SCANLINES_PER_BUCKET 8 +#define CACHE_LINE_SIZE 64 // this is a general guess +#define TOTAL_BUCKETS (512 / SCANLINES_PER_BUCKET) +#define UNITS_PER_POLY (100 / SCANLINES_PER_BUCKET) + + + +//************************************************************************** +// TYPE DEFINITIONS +//************************************************************************** + +//------------------------------------------------- +// global helpers for float base types +//------------------------------------------------- + +inline float poly_floor(float x) { return floorf(x); } +inline float poly_abs(float x) { return fabsf(x); } +inline float poly_recip(float x) { return 1.0f / x; } + + +//------------------------------------------------- +// global helpers for double base types +//------------------------------------------------- + +inline double poly_floor(double x) { return floor(x); } +inline double poly_abs(double x) { return fabs(x); } +inline double poly_recip(double x) { return 1.0 / x; } + + +// poly_manager is a template class +template<typename _BaseType, class _ObjectData, int _MaxParams, int _MaxPolys> +class poly_manager +{ +public: + // 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 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, const extent_t &, const _ObjectData &, int)> render_delegate; + + // construction/destruction + poly_manager(running_machine &machine, UINT8 flags = 0); + virtual ~poly_manager(); + + // getters + running_machine &machine() const { return m_machine; } + + // 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 render_tile(const rectangle &cliprect, render_delegate callback, int paramcount, const vertex_t &v1, const vertex_t &v2); + + // triangles + UINT32 render_triangle(const rectangle &cliprect, render_delegate callback, int paramcount, const vertex_t &v1, const vertex_t &v2, const vertex_t &v3); + UINT32 render_triangle_fan(const rectangle &cliprect, render_delegate callback, int paramcount, int numverts, const vertex_t *v); + UINT32 render_triangle_strip(const rectangle &cliprect, render_delegate callback, int paramcount, int numverts, const vertex_t *v); + UINT32 render_triangle_custom(const rectangle &cliprect, render_delegate callback, int startscanline, int numscanlines, const extent_t *extents); + + // polygons + template<int _NumVerts> + UINT32 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: + // 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 + { + volatile UINT32 count_next; // number of scanlines and index of next item to process + polygon_info * polygon; // pointer to polygon + INT16 scanline; // starting scanline + UINT16 previtem; // index of previous item in the same bucket + #ifndef PTR64 + UINT32 dummy; // pad to 16 bytes + #endif + extent_t extent[SCANLINES_PER_BUCKET]; // array of scanline extents + }; + + // 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(auto_alloc_array_clear(machine, UINT8, k_itemsize * _Count)), + m_next(0), + m_max(0), + m_waits(0) { } + + // destruction + ~poly_array() { auto_free(m_manager.machine(), m_base); } + + // operators + _Type &operator[](int index) const { assert(index >= 0 && index < _Count); return *reinterpret_cast<_Type *>(m_base + 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 *>(&item) - m_base) / 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 + 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; + UINT8 * 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, MIN(_MaxPolys * UNITS_PER_POLY, 65535)> unit_array; + + // round in a cross-platform consistent manner + inline INT32 round_coordinate(_BaseType value) + { + INT32 result = poly_floor(value); + 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; + 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 m_flags; // flags + + // buckets + UINT16 m_unit_bucket[TOTAL_BUCKETS]; // buckets for tracking unit usage + + // statistics + UINT32 m_tiles; // number of tiles queued + UINT32 m_triangles; // number of triangles queued + UINT32 m_quads; // number of quads queued + UINT64 m_pixels; // number of pixels rendered +#if KEEP_STATISTICS + UINT32 m_conflicts[WORK_MAX_THREADS]; // number of conflicts found, per thread + UINT32 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 flags) + : m_machine(machine), + m_queue(NULL), + m_polygon(machine, *this), + m_object(machine, *this), + m_unit(machine, *this), + m_flags(flags), + m_triangles(0), + m_quads(0), + m_pixels(0) +{ +#if KEEP_STATISTICS + memset(m_conflicts, 0, sizeof(m_conflicts)); + memset(m_resolved, 0, sizeof(m_resolved)); +#endif + + // create the work queue + if (!(flags & POLYFLAG_NO_WORK_QUEUE)) + m_queue = osd_work_queue_alloc(WORK_QUEUE_FLAG_MULTI | WORK_QUEUE_FLAG_HIGH_FREQ); + + // 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_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)(m_pixels / 1000000000), (UINT32)(m_pixels % 1000000000)); + else + printf("Total pixels = %d\n", (UINT32)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 != NULL) + 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 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 unitnum = polygon.m_owner->m_unit.indexof(unit); + UINT32 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 (compare_exchange32((volatile INT32 *)&prevunit.count_next, orig_count_next, new_count_next) != orig_count_next); + +#if KEEP_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 (compare_exchange32((volatile INT32 *)&unit.count_next, orig_count_next, 0) != orig_count_next); + + // 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 NULL; +} + + +//------------------------------------------------- +// 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 (LOG_WAITS) + time = get_profile_ticks(); + + // wait for all pending work items to complete + if (m_queue != NULL) + 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 (LOG_WAITS) + { + time = get_profile_ticks() - time; + if (time > LOG_WAIT_THRESHOLD) + 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 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 v1y = round_coordinate(v1->y); + INT32 v2y = round_coordinate(v2->y); + + // clip coordinates + INT32 v1yclip = v1y; + INT32 v2yclip = v2y + ((m_flags & POLYFLAG_INCLUDE_BOTTOM_EDGE) ? 1 : 0); + v1yclip = MAX(v1yclip, cliprect.min_y); + v2yclip = MIN(v2yclip, cliprect.max_y + 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 istartx = round_coordinate(v1->x); + INT32 istopx = round_coordinate(v2->x); + + // force start < stop + if (istartx > istopx) + { + INT32 temp = istartx; + istartx = istopx; + istopx = temp; + } + + // include the right edge if requested + if (m_flags & POLYFLAG_INCLUDE_RIGHT_EDGE) + istopx++; + + // apply left/right clipping + if (istartx < cliprect.min_x) + istartx = cliprect.min_x; + if (istopx > cliprect.max_x) + istopx = cliprect.max_x + 1; + if (istartx >= istopx) + return 0; + + // compute the X extents for each scanline + INT32 pixels = 0; + UINT32 startunit = m_unit.count(); + INT32 scaninc = 1; + for (INT32 curscan = v1yclip; curscan < v2yclip; curscan += scaninc) + { + UINT32 bucketnum = ((UINT32)curscan / SCANLINES_PER_BUCKET) % TOTAL_BUCKETS; + UINT32 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)curscan % SCANLINES_PER_BUCKET; + + // fill in the work unit basics + unit.polygon = &polygon; + unit.count_next = 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 = NULL; + 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 != NULL) + 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 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 *tv = v1; + v1 = v2; + v2 = tv; + } + } + + // compute some integral X/Y vertex values + INT32 v1y = round_coordinate(v1->y); + INT32 v3y = round_coordinate(v3->y); + + // clip coordinates + INT32 v1yclip = v1y; + INT32 v3yclip = v3y + ((m_flags & POLYFLAG_INCLUDE_BOTTOM_EDGE) ? 1 : 0); + v1yclip = MAX(v1yclip, cliprect.min_y); + v3yclip = MIN(v3yclip, cliprect.max_y + 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); + } + } + } + + // compute the X extents for each scanline + INT32 pixels = 0; + UINT32 startunit = m_unit.count(); + INT32 scaninc = 1; + for (INT32 curscan = v1yclip; curscan < v3yclip; curscan += scaninc) + { + UINT32 bucketnum = ((UINT32)curscan / SCANLINES_PER_BUCKET) % TOTAL_BUCKETS; + UINT32 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)curscan % SCANLINES_PER_BUCKET; + + // fill in the work unit basics + unit.polygon = &polygon; + unit.count_next = 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 istartx = round_coordinate(startx); + INT32 istopx = round_coordinate(stopx); + + // force start < stop + if (istartx > istopx) + { + INT32 temp = istartx; + istartx = istopx; + istopx = temp; + } + + // include the right edge if requested + if (m_flags & POLYFLAG_INCLUDE_RIGHT_EDGE) + istopx++; + + // apply left/right clipping + if (istartx < cliprect.min_x) + istartx = cliprect.min_x; + if (istopx > cliprect.max_x) + istopx = cliprect.max_x + 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 = NULL; + 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 != NULL) + 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 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 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 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 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 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 v1yclip = MAX(startscanline, cliprect.min_y); + INT32 v3yclip = MIN(startscanline + numscanlines, cliprect.max_y + 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 pixels = 0; + UINT32 startunit = m_unit.count(); + INT32 scaninc = 1; + for (INT32 curscan = v1yclip; curscan < v3yclip; curscan += scaninc) + { + UINT32 bucketnum = ((UINT32)curscan / SCANLINES_PER_BUCKET) % TOTAL_BUCKETS; + UINT32 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)curscan % SCANLINES_PER_BUCKET; + + // fill in the work unit basics + unit.polygon = &polygon; + unit.count_next = 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 istartx = srcextent.startx, istopx = srcextent.stopx; + + // apply left/right clipping + if (istartx < cliprect.min_x) + istartx = cliprect.min_x; + if (istartx > cliprect.max_x) + istartx = cliprect.max_x + 1; + if (istopx < cliprect.min_x) + istopx = cliprect.min_x; + if (istopx > cliprect.max_x) + istopx = cliprect.max_x + 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 != NULL) + 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 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 miny = round_coordinate(v[minv].y); + INT32 maxy = round_coordinate(v[maxv].y); + + // clip coordinates + INT32 minyclip = miny; + INT32 maxyclip = maxy + ((m_flags & POLYFLAG_INCLUDE_BOTTOM_EDGE) ? 1 : 0); + minyclip = MAX(minyclip, cliprect.min_y); + maxyclip = MIN(maxyclip, cliprect.max_y + 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 pixels = 0; + UINT32 startunit = m_unit.count(); + INT32 scaninc = 1; + for (INT32 curscan = minyclip; curscan < maxyclip; curscan += scaninc) + { + UINT32 bucketnum = ((UINT32)curscan / SCANLINES_PER_BUCKET) % TOTAL_BUCKETS; + UINT32 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)curscan % SCANLINES_PER_BUCKET; + + // fill in the work unit basics + unit.polygon = &polygon; + unit.count_next = 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 istartx = round_coordinate(startx); + INT32 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 & POLYFLAG_INCLUDE_RIGHT_EDGE) + istopx++; + + // apply left/right clipping + if (istartx < cliprect.min_x) + { + for (int paramnum = 0; paramnum < paramcount; paramnum++) + extent.param[paramnum].start += (cliprect.min_x - istartx) * extent.param[paramnum].dpdx; + istartx = cliprect.min_x; + } + if (istopx > cliprect.max_x) + istopx = cliprect.max_x + 1; + + // set the extent and update the total pixel count + if (istartx >= istopx) + istartx = istopx = 0; + extent.startx = istartx; + extent.stopx = istopx; + extent.userdata = NULL; + pixels += istopx - istartx; + } + } + + // enqueue the work items + if (m_queue != NULL) + 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; +} + +#endif // __POLYNEW_H__ |