/* * Copyright 2011-2019 Branimir Karadzic. All rights reserved. * License: https://github.com/bkaradzic/bgfx#license-bsd-2-clause */ #include #include #include #include #include #include "config.h" #include "topology.h" namespace bgfx { template static uint32_t topologyConvertTriListFlipWinding(void* _dst, uint32_t _dstSize, const IndexT* _indices, uint32_t _numIndices) { if (NULL == _dst) { return _numIndices; } IndexT* dst = (IndexT*)_dst; IndexT* end = &dst[_dstSize/sizeof(IndexT)]; for (uint32_t ii = 0; ii < _numIndices && dst < end; ii += 3, dst += 3) { const IndexT* tri = &_indices[ii]; IndexT i0 = tri[0], i1 = tri[1], i2 = tri[2]; dst[0] = i0; dst[1] = i2; dst[2] = i1; } return _numIndices; } inline bool isEven(uint32_t _num) { return 0 == (_num & 1); } template static uint32_t topologyConvertTriStripFlipWinding(void* _dst, uint32_t _dstSize, const IndexT* _indices, uint32_t _numIndices) { const uint32_t numIndices = isEven(_numIndices) ? _numIndices + 1 : _numIndices; if (NULL != _dst) { return numIndices; } IndexT* dst = (IndexT*)_dst; IndexT* end = &dst[_dstSize/sizeof(IndexT)]; if (isEven(_numIndices) ) { *dst++ = _indices[_numIndices-1]; } for (uint32_t ii = 1; ii <= _numIndices && dst < end; ++ii) { *dst++ = _indices[_numIndices - ii]; } return numIndices; } template static uint32_t topologyConvertTriListToLineList(void* _dst, uint32_t _dstSize, const IndexT* _indices, uint32_t _numIndices, IndexT* _temp, SortT* _tempSort) { // Create all line pairs and sort indices. IndexT* dst = _temp; for (uint32_t ii = 0; ii < _numIndices; ii += 3) { const IndexT* tri = &_indices[ii]; IndexT i0 = tri[0], i1 = tri[1], i2 = tri[2]; if (i0 > i1) { bx::swap(i0, i1); } if (i1 > i2) { bx::swap(i1, i2); } if (i0 > i1) { bx::swap(i0, i1); } BX_CHECK(i0 < i1 && i1 < i2, ""); dst[1] = i0; dst[0] = i1; dst[3] = i1; dst[2] = i2; dst[5] = i0; dst[4] = i2; dst += 6; } // Sort all line pairs. SortT* sorted = (SortT*)_temp; bx::radixSort(sorted, _tempSort, _numIndices); uint32_t num = 0; // Remove all line pair duplicates. if (NULL == _dst) { SortT last = sorted[0]; for (uint32_t ii = 1; ii < _numIndices; ++ii) { if (last != sorted[ii]) { num += 2; last = sorted[ii]; } } num += 2; } else { dst = (IndexT*)_dst; IndexT* end = &dst[_dstSize/sizeof(IndexT)]; SortT last = sorted[0]; { union Un { SortT key; struct { IndexT i0; IndexT i1; } u16; } un = { sorted[0] }; dst[0] = un.u16.i0; dst[1] = un.u16.i1; dst += 2; } for (uint32_t ii = 1; ii < _numIndices && dst < end; ++ii) { if (last != sorted[ii]) { union Un { SortT key; struct { IndexT i0; IndexT i1; } u16; } un = { sorted[ii] }; dst[0] = un.u16.i0; dst[1] = un.u16.i1; dst += 2; last = sorted[ii]; } } num = uint32_t(dst - (IndexT*)_dst); } return num; } template static uint32_t topologyConvertTriListToLineList(void* _dst, uint32_t _dstSize, const IndexT* _indices, uint32_t _numIndices, bx::AllocatorI* _allocator) { IndexT* temp = (IndexT*)BX_ALLOC(_allocator, _numIndices*2*sizeof(IndexT)*2); SortT* tempSort = (SortT*)&temp[_numIndices*2]; uint32_t num = topologyConvertTriListToLineList(_dst, _dstSize, _indices, _numIndices, temp, tempSort); BX_FREE(_allocator, temp); return num; } template static uint32_t topologyConvertTriStripToTriList(void* _dst, uint32_t _dstSize, const IndexT* _indices, uint32_t _numIndices) { IndexT* dst = (IndexT*)_dst; IndexT* end = &dst[_dstSize/sizeof(IndexT)]; for (uint32_t ii = 0, num = _numIndices-2; ii < num && dst < end; ++ii) { IndexT i0 = _indices[ii+0]; IndexT i1 = _indices[ii+1]; IndexT i2 = _indices[ii+2]; if (i0 != i1 && i1 != i2) { dst[0] = i0; dst[1] = i1; dst[2] = i2; dst += 3; } } return uint32_t(dst - (IndexT*)_dst); } template static uint32_t topologyConvertLineStripToLineList(void* _dst, uint32_t _dstSize, const IndexT* _indices, uint32_t _numIndices) { IndexT* dst = (IndexT*)_dst; IndexT* end = &dst[_dstSize/sizeof(IndexT)]; IndexT i0 = _indices[0]; for (uint32_t ii = 1; ii < _numIndices && dst < end; ++ii) { IndexT i1 = _indices[ii]; if (i0 != i1) { dst[0] = i0; dst[1] = i1; dst += 2; i0 = i1; } } return uint32_t(dst - (IndexT*)_dst); } uint32_t topologyConvert( TopologyConvert::Enum _conversion , void* _dst , uint32_t _dstSize , const void* _indices , uint32_t _numIndices , bool _index32 , bx::AllocatorI* _allocator ) { switch (_conversion) { case TopologyConvert::TriStripToTriList: if (_index32) { return topologyConvertTriStripToTriList(_dst, _dstSize, (const uint32_t*)_indices, _numIndices); } return topologyConvertTriStripToTriList(_dst, _dstSize, (const uint16_t*)_indices, _numIndices); case TopologyConvert::TriListFlipWinding: if (_index32) { return topologyConvertTriListFlipWinding(_dst, _dstSize, (const uint32_t*)_indices, _numIndices); } return topologyConvertTriListFlipWinding(_dst, _dstSize, (const uint16_t*)_indices, _numIndices); case TopologyConvert::TriStripFlipWinding: if (_index32) { return topologyConvertTriStripFlipWinding(_dst, _dstSize, (const uint32_t*)_indices, _numIndices); } return topologyConvertTriStripFlipWinding(_dst, _dstSize, (const uint16_t*)_indices, _numIndices); case TopologyConvert::TriListToLineList: if (NULL == _allocator) { return 0; } if (_index32) { return topologyConvertTriListToLineList(_dst, _dstSize, (const uint32_t*)_indices, _numIndices, _allocator); } return topologyConvertTriListToLineList(_dst, _dstSize, (const uint16_t*)_indices, _numIndices, _allocator); case TopologyConvert::LineStripToLineList: if (_index32) { return topologyConvertLineStripToLineList(_dst, _dstSize, (const uint32_t*)_indices, _numIndices); } return topologyConvertLineStripToLineList(_dst, _dstSize, (const uint16_t*)_indices, _numIndices); default: break; } return 0; } inline float fmin3(float _a, float _b, float _c) { return bx::min(_a, _b, _c); } inline float fmax3(float _a, float _b, float _c) { return bx::max(_a, _b, _c); } inline float favg3(float _a, float _b, float _c) { return (_a + _b + _c) * 1.0f/3.0f; } const bx::Vec3 vertexPos(const void* _vertices, uint32_t _stride, uint32_t _index) { const uint8_t* vertices = (const uint8_t*)_vertices; return bx::load(&vertices[_index*_stride]); } inline float distanceDir(const float* _dir, const void* _vertices, uint32_t _stride, uint32_t _index) { return bx::dot(vertexPos(_vertices, _stride, _index), bx::load(_dir) ); } inline float distancePos(const float* _pos, const void* _vertices, uint32_t _stride, uint32_t _index) { const bx::Vec3 tmp = bx::sub(bx::load(_pos), vertexPos(_vertices, _stride, _index) ); return bx::sqrt(bx::dot(tmp, tmp) ); } typedef float (*KeyFn)(float, float, float); typedef float (*DistanceFn)(const float*, const void*, uint32_t, uint32_t); template inline void calcSortKeys( uint32_t* _keys , uint32_t* _values , const float _dirOrPos[3] , const void* _vertices , uint32_t _stride , const IndexT* _indices , uint32_t _num ) { for (uint32_t ii = 0; ii < _num; ++ii) { const uint32_t idx0 = _indices[0]; const uint32_t idx1 = _indices[1]; const uint32_t idx2 = _indices[2]; _indices += 3; float distance0 = dfn(_dirOrPos, _vertices, _stride, idx0); float distance1 = dfn(_dirOrPos, _vertices, _stride, idx1); float distance2 = dfn(_dirOrPos, _vertices, _stride, idx2); uint32_t ui = bx::floatToBits(kfn(distance0, distance1, distance2) ); _keys[ii] = bx::floatFlip(ui) ^ xorBits; _values[ii] = ii; } } template void topologySortTriList( TopologySort::Enum _sort , IndexT* _dst , uint32_t* _keys , uint32_t* _values , uint32_t* _tempKeys , uint32_t* _tempValues , uint32_t _num , const float _dir[3] , const float _pos[3] , const void* _vertices , uint32_t _stride , const IndexT* _indices ) { using namespace bx; switch (_sort) { default: case TopologySort::DirectionFrontToBackMin: calcSortKeys(_keys, _values, _dir, _vertices, _stride, _indices, _num); break; case TopologySort::DirectionFrontToBackAvg: calcSortKeys(_keys, _values, _dir, _vertices, _stride, _indices, _num); break; case TopologySort::DirectionFrontToBackMax: calcSortKeys(_keys, _values, _dir, _vertices, _stride, _indices, _num); break; case TopologySort::DirectionBackToFrontMin: calcSortKeys(_keys, _values, _dir, _vertices, _stride, _indices, _num); break; case TopologySort::DirectionBackToFrontAvg: calcSortKeys(_keys, _values, _dir, _vertices, _stride, _indices, _num); break; case TopologySort::DirectionBackToFrontMax: calcSortKeys(_keys, _values, _dir, _vertices, _stride, _indices, _num); break; case TopologySort::DistanceFrontToBackMin: calcSortKeys(_keys, _values, _pos, _vertices, _stride, _indices, _num); break; case TopologySort::DistanceFrontToBackAvg: calcSortKeys(_keys, _values, _pos, _vertices, _stride, _indices, _num); break; case TopologySort::DistanceFrontToBackMax: calcSortKeys(_keys, _values, _pos, _vertices, _stride, _indices, _num); break; case TopologySort::DistanceBackToFrontMin: calcSortKeys(_keys, _values, _pos, _vertices, _stride, _indices, _num); break; case TopologySort::DistanceBackToFrontAvg: calcSortKeys(_keys, _values, _pos, _vertices, _stride, _indices, _num); break; case TopologySort::DistanceBackToFrontMax: calcSortKeys(_keys, _values, _pos, _vertices, _stride, _indices, _num); break; } radixSort(_keys, _tempKeys, _values, _tempValues, _num); IndexT* sorted = _dst; for (uint32_t ii = 0; ii < _num; ++ii) { uint32_t face = _values[ii]*3; const IndexT idx0 = _indices[face+0]; const IndexT idx1 = _indices[face+1]; const IndexT idx2 = _indices[face+2]; sorted[0] = idx0; sorted[1] = idx1; sorted[2] = idx2; sorted += 3; } } void topologySortTriList( TopologySort::Enum _sort , void* _dst , uint32_t _dstSize , const float _dir[3] , const float _pos[3] , const void* _vertices , uint32_t _stride , const void* _indices , uint32_t _numIndices , bool _index32 , bx::AllocatorI* _allocator ) { uint32_t indexSize = _index32 ? sizeof(uint32_t) : sizeof(uint16_t) ; uint32_t num = bx::uint32_min(_numIndices*indexSize, _dstSize)/(indexSize*3); uint32_t* temp = (uint32_t*)BX_ALLOC(_allocator, sizeof(uint32_t)*num*4); uint32_t* keys = &temp[num*0]; uint32_t* values = &temp[num*1]; uint32_t* tempKeys = &temp[num*2]; uint32_t* tempValues = &temp[num*3]; if (_index32) { topologySortTriList( _sort , (uint32_t*)_dst , keys , values , tempKeys , tempValues , num , _dir , _pos , _vertices , _stride , (const uint32_t*)_indices ); } else { topologySortTriList( _sort , (uint16_t*)_dst , keys , values , tempKeys , tempValues , num , _dir , _pos , _vertices , _stride , (const uint16_t*)_indices ); } BX_FREE(_allocator, temp); } } //namespace bgfx