From 4fc0e05ebd07f34b1c7e714115e2a572725abdf4 Mon Sep 17 00:00:00 2001 From: xy Date: Sat, 14 Jul 2012 21:55:20 +0800 Subject: [PATCH] New create widen region algorithm. --- src/subtitles/Rasterizer.cpp | 13 +- src/subtitles/subtitles_vs2010.vcxproj | 3 + src/subtitles/subtitles_vs2010.vcxproj.filters | 9 + src/subtitles/xy_circular_array_queue.h | 173 +++++++ src/subtitles/xy_widen_region.cpp | 595 +++++++++++++++++++++++++ src/subtitles/xy_widen_regoin.h | 21 + 6 files changed, 804 insertions(+), 10 deletions(-) create mode 100644 src/subtitles/xy_circular_array_queue.h create mode 100644 src/subtitles/xy_widen_region.cpp create mode 100644 src/subtitles/xy_widen_regoin.h diff --git a/src/subtitles/Rasterizer.cpp b/src/subtitles/Rasterizer.cpp index 32cdebd..635e36b 100644 --- a/src/subtitles/Rasterizer.cpp +++ b/src/subtitles/Rasterizer.cpp @@ -29,6 +29,7 @@ #include "xy_logger.h" #include #include "xy_bitmap.h" +#include "xy_widen_regoin.h" #ifndef _MAX /* avoid collision with common (nonconforming) macros */ #define _MAX (std::max) @@ -40,7 +41,6 @@ #define _IMPL_MIN _MIN #endif - //NOTE: signed or unsigned affects the result seriously #define COMBINE_AYUV(a, y, u, v) ((((((((int)(a))<<8)|y)<<8)|u)<<8)|v) @@ -2430,8 +2430,6 @@ bool ScanLineData::ScanConvert(const PathData& path_data, const CSize& size) return true; } -using namespace std; - void ScanLineData::DeleteOutlines() { mOutline.clear(); @@ -2447,13 +2445,8 @@ bool ScanLineData2::CreateWidenedRegion(int rx, int ry) const tSpanBuffer& out_line = m_scan_line_data->mOutline; if (ry > 0) { - // Do a half circle. - // _OverlapRegion mirrors this so both halves are done. - for(int y = -ry; y <= ry; ++y) - { - int x = (int)(0.5 + sqrt(float(ry*ry - y*y)) * float(rx)/float(ry)); - OverlapRegion(mWideOutline, out_line, x, y); - } + WidenRegionCreater *widen_region_creater = WidenRegionCreater::GetDefaultWidenRegionCreater(); + widen_region_creater->xy_overlap_region(&mWideOutline, out_line, rx, ry); } else if (ry == 0 && rx > 0) { diff --git a/src/subtitles/subtitles_vs2010.vcxproj b/src/subtitles/subtitles_vs2010.vcxproj index 19080d5..797fcd5 100644 --- a/src/subtitles/subtitles_vs2010.vcxproj +++ b/src/subtitles/subtitles_vs2010.vcxproj @@ -212,6 +212,7 @@ NotUsing + @@ -240,10 +241,12 @@ + + diff --git a/src/subtitles/subtitles_vs2010.vcxproj.filters b/src/subtitles/subtitles_vs2010.vcxproj.filters index a58ae44..726ea61 100644 --- a/src/subtitles/subtitles_vs2010.vcxproj.filters +++ b/src/subtitles/subtitles_vs2010.vcxproj.filters @@ -93,6 +93,9 @@ Source Files + + Source Files + @@ -185,5 +188,11 @@ Header Files + + Source Files + + + Header Files + \ No newline at end of file diff --git a/src/subtitles/xy_circular_array_queue.h b/src/subtitles/xy_circular_array_queue.h new file mode 100644 index 0000000..56a75cd --- /dev/null +++ b/src/subtitles/xy_circular_array_queue.h @@ -0,0 +1,173 @@ +#ifndef __XY_CIRCULAR_ARRAY_QUEUE_HPP_47831C93_EDAA_44B9_94F2_6FF36839D1A6__ +#define __XY_CIRCULAR_ARRAY_QUEUE_HPP_47831C93_EDAA_44B9_94F2_6FF36839D1A6__ + +template +class XYCircularArrayQueue +{ +public: + typedef ElementType value_type; + typedef ElementType& reference; + typedef const ElementType& const_reference; +public: + /*** + * @brief Default constructor creates no elements. + **/ + explicit XYCircularArrayQueue() + :_elements(NULL), + _head(0), + _tail(0), + _CAPACITY(0) + { + } + + ~XYCircularArrayQueue() + { + delete[] _elements; + } + + inline int init(size_t capacity) + { + _CAPACITY = capacity; + _elements = new value_type[_CAPACITY]; + return _elements ? 0 : -1; + } + + inline size_t capacity() + { + return _CAPACITY; + } + + inline bool full() const + { + return size() >= (_CAPACITY -1); + } + + inline bool empty() const + { + return _head == _tail; + } + + /*** + * @return: the number of elements in the @queue. + **/ + inline size_t size() const + { + return (_CAPACITY -_head+_tail) %_CAPACITY; + } + + /*** + * @return: the number of free elements in the @queue. + **/ + inline size_t free() const + { + return _CAPACITY - (_CAPACITY -_head+_tail) %_CAPACITY; + } + + /*** + * @return: a read/write reference to the i-th element. + **/ + inline reference get_at(int i) + { + i += _head; + i %= _CAPACITY; + return _elements[i]; + } + + /*** + * @return: a read-only reference to the i-th element. + **/ + inline const_reference get_at(int i) const + { + i += _head; + i %= _CAPACITY; + return _elements[i]; + } + + /*** + * @return: a read/write reference to the last element + **/ + inline reference back() + { + return _elements[(_CAPACITY +_tail -1) % _CAPACITY]; + } + + /*** + * @return: a read-only reference to the last element + **/ + inline const_reference back() const + { + return _elements[(_CAPACITY +_tail -1) % _CAPACITY]; + } + + /*** + * @return: 0 if succeeded, -1 if failed + **/ + inline int push_back(const_reference value) + { + if(size() == (_CAPACITY -1)) + { + return -1; + } + else + { + _elements[_tail] = value; + _tail = (_tail+1) % _CAPACITY; + return 0; + } + } + + inline reference inc_1_at_tail() + { + _tail++; + _tail += _CAPACITY; + _tail %= _CAPACITY; + return _elements[(_CAPACITY +_tail -1) % _CAPACITY]; + } + + inline void pop_front() + { + if(empty()) + { + return; + } + else + { + _head = (_head + 1) % _CAPACITY; + } + } + + inline void pop_back() + { + if(empty()) + { + return; + } + else + { + _tail = (_tail - 1 + _CAPACITY) % _CAPACITY; + } + } + + inline void pop_last_n(int n) + { + if (size() +#include "xy_circular_array_queue.h" +#include + +//terminology +// @left arc : left part of an ellipse +// @right arc: right part of an ellipse +// @link arc : curve composed by all left most points of a series of left arc , or all right most points of a series of right arc +// @cross_line of arc a and b (a.y < b.y): +// if both a and b are left arc, @cross_line is the max line that satisfied: +// a(line)< b(line) on line<@cross_line, +// and +// a(line)>=b(line) on line>=@cross_line +// if both a and b are right arc, @cross_line is the max line that satisfied: +// a(line)> b(line) on line<@cross_line, +// and +// a(line)<=b(line) on line>=@cross_line + +static const int MIN_CROSS_LINE = (-2147483647 - 1); +static const int MAX_CROSS_LINE = 0x7fffffff; +static const int MAX_X = 0x7fffffff; + +typedef unsigned __int64 XY_POINT; +#define XY_POINT_X(point) ((point)&0xffffffff) +#define XY_POINT_Y(point) ((point)>>32) +#define XY_POINT_SET(point,x,y) ((point)=(((long long)(y)<<32)|(x))) + +struct LinkArcItem +{ + LinkArcItem():dead_line(0),arc_center(0){} + + XY_POINT arc_center; + int dead_line; +}; + +typedef XYCircularArrayQueue LinkArc; + +struct LinkSpan +{ + LinkArc left; + LinkArc right; +}; + +typedef CAtlList LinkSpanList; + +typedef tSpan Span; +typedef tSpanBuffer SpanBuffer; +#define SPAN_LEFT(span) ((span).first) +#define SPAN_RIGHT(span) ((span).second) +#define SPAN_PTR_LEFT(span) ((span)->first) +#define SPAN_PTR_RIGHT(span) ((span)->second) + +struct XyEllipse +{ +public: + XyEllipse(); + ~XyEllipse(); + + /*** + * ry must >0 and rx must >=0 + **/ + int init(int rx, int ry); + + inline int get_left_arc_x(int y) const; + inline int get_left_arc_x(XY_POINT center, int y) const; + + inline int get_right_arc_x(int y) const; + inline int get_right_arc_x(XY_POINT center, int y) const; + + int cross_left(XY_POINT c1, XY_POINT base) const; + int cross_right(XY_POINT c1, XY_POINT base) const; + + int init_cross_point(); + + int m_rx, m_ry; + int *m_left_arc; + int *m_left_arc_base; + + int *m_cross_matrix; + int *m_cross_matrix_base; +private: + XyEllipse(const XyEllipse&); + void operator=(const XyEllipse&); +}; + +class WidenRegionCreaterImpl +{ +public: + WidenRegionCreaterImpl(); + ~WidenRegionCreaterImpl(); + + void xy_overlap_region(SpanBuffer* dst, const SpanBuffer& src, int rx, int ry); +private: + int cross_left(const LinkArc& arc, XY_POINT center);//return <0 if arc(o)inner_pl, else return cross_line + + void add_left(LinkArc* arc, XY_POINT center); + void add_right(LinkArc* arc, XY_POINT center); + void add_span(LinkSpan* spans, const Span& span); + void add_line(SpanBuffer* dst, LinkSpanList& spans, int cur_line, int dead_line);//add all linexy_overlap_region(dst, src, rx, ry); +} + +// +// WidenRegionCreaterImpl +// + +WidenRegionCreaterImpl::WidenRegionCreaterImpl(): m_ellipse(NULL) +{ +} + +WidenRegionCreaterImpl::~WidenRegionCreaterImpl() +{ + delete m_ellipse; +} + +void WidenRegionCreaterImpl::xy_overlap_region(SpanBuffer* dst, const SpanBuffer& src, int rx, int ry) +{ + if (m_ellipse!=NULL && (m_ellipse->m_rx!=rx || m_ellipse->m_ry!=ry)) + { + delete m_ellipse; + m_ellipse = NULL; + } + if (m_ellipse==NULL) + { + m_ellipse = new XyEllipse(); + if (m_ellipse==NULL) + { + ASSERT(0); + return; + } + int rv = m_ellipse->init(rx, ry); + if (rv<0) + { + ASSERT(0); + return; + } + } + + LinkSpanList link_span_list; + POSITION pos=NULL; + int dst_line = 0; + + SpanBuffer::const_iterator it_src = src.begin(); + SpanBuffer::const_iterator it_src_end = src.end(); + + LinkSpan &sentinel = link_span_list.GetAt(link_span_list.AddTail()); + sentinel.left.init(2*ry+2); + sentinel.right.init(2*ry+2); + LinkArcItem& item = sentinel.left.inc_1_at_tail(); + XY_POINT_SET(item.arc_center, MAX_X, 0); + item.dead_line = MAX_CROSS_LINE; + + for ( ;it_src!=it_src_end; it_src++) + { + const XY_POINT &left = SPAN_PTR_LEFT(it_src); + const XY_POINT &right = SPAN_PTR_RIGHT(it_src); + int line = XY_POINT_Y(left); //fix me + if (line-ry>dst_line) + { + add_line(dst, link_span_list, dst_line, line - ry); + dst_line = line - ry; + ASSERT(!link_span_list.IsEmpty() && !link_span_list.GetTail().left.empty()); + ASSERT(XY_POINT_X(link_span_list.GetTail().left.get_at(0).arc_center)==MAX_X); + XY_POINT_SET(link_span_list.GetTail().left.get_at(0).arc_center, MAX_X, line-1);//update sentinel + pos = link_span_list.GetHeadPosition(); + } + while(true) + { + LinkSpan &spans = link_span_list.GetAt(pos); + LinkArc &arc = spans.left; + int y = cross_left(arc, left); + if (y>ry)//fix me + { + link_span_list.GetNext(pos); + continue; + } + else if ( y>=-ry )//fix me + { + add_span(&spans, *it_src); + link_span_list.GetNext(pos); + break; + } + else + { + LinkSpan &new_span = link_span_list.GetAt(link_span_list.InsertBefore(pos, LinkSpan())); + new_span.left.init(2*ry+2); + LinkArcItem& item = new_span.left.inc_1_at_tail(); + + item.arc_center = SPAN_PTR_LEFT(it_src); + item.dead_line = line+ry+1; + + new_span.right.init(2*ry+2); + LinkArcItem& item2 = new_span.right.inc_1_at_tail(); + item2.arc_center = SPAN_PTR_RIGHT(it_src); + item2.dead_line = line+ry+1; + break; + } + } + } + add_line(dst, link_span_list, dst_line, MAX_CROSS_LINE); +} + +int WidenRegionCreaterImpl::cross_left(const LinkArc& arc, XY_POINT center) +{ + ASSERT(!arc.empty()); + int y = m_ellipse->cross_left(arc.back().arc_center, center); + if (y>=MAX_CROSS_LINE) + { + return MAX_CROSS_LINE; + } + else + { + y = m_ellipse->cross_left(arc.get_at(0).arc_center, center); + if (y<=MIN_CROSS_LINE) + { + return MIN_CROSS_LINE; + } + } + return 0; +} + +void WidenRegionCreaterImpl::add_span(LinkSpan* spans, const Span& span ) +{ + ASSERT(spans); + add_left(&spans->left, SPAN_LEFT(span)); + add_right(&spans->right, SPAN_RIGHT(span)); +} + +void WidenRegionCreaterImpl::add_left( LinkArc* arc, XY_POINT center ) +{ + int rx = m_ellipse->m_rx; + int ry = m_ellipse->m_ry; + ASSERT(arc); + ASSERT(!arc->empty()&& m_ellipse->cross_left(arc->get_at(0).arc_center, center)>=-ry ); + int y = 0; + int i = 0; + int line = XY_POINT_Y(center); + for (i=arc->size()-1;i>=1;i--) + { + y = m_ellipse->cross_left( arc->get_at(i).arc_center, center ); + if( y>ry )//not cross + { + break; + } + else if ( y+line>arc->get_at(i-1).dead_line ) + { + arc->get_at(i).dead_line = y+line; + break; + } + else + { + arc->pop_back(); + } + } + if (i==0) + { + y = m_ellipse->cross_left( arc->get_at(0).arc_center, center ); + ASSERT(y>=-ry && y+line<=arc->get_at(0).dead_line); + arc->get_at(0).dead_line = y + line; + } + LinkArcItem& item = arc->inc_1_at_tail(); + item.arc_center = center; + item.dead_line = line + ry + 1; +} + +void WidenRegionCreaterImpl::add_right( LinkArc* arc, XY_POINT center ) +{ + int rx = m_ellipse->m_rx; + int ry = m_ellipse->m_ry; + ASSERT(arc); + ASSERT(!arc->empty()); + int y = 0; + int i = 0; + int line = XY_POINT_Y(center); + for (i=arc->size()-1;i>=1;i--) + { + y = m_ellipse->cross_right( arc->get_at(i).arc_center, center ); + if( y>ry )//not cross + { + break; + } + else if ( y+line>arc->get_at(i-1).dead_line ) + { + arc->get_at(i).dead_line = y+line; + break; + } + else + { + arc->pop_back(); + } + } + if (i==0) + { + y = m_ellipse->cross_right( arc->get_at(0).arc_center, center ); + if (y<-ry) + { + arc->pop_back(); + } + else if (yget_at(0).dead_line); + arc->get_at(0).dead_line = y + line; + } + } + LinkArcItem& item = arc->inc_1_at_tail(); + item.arc_center = center; + item.dead_line = line + ry + 1; +} + +void WidenRegionCreaterImpl::add_line( SpanBuffer* dst, LinkSpanList& spans, int cur_dst_line, int dead_line ) +{ + ASSERT(dst); + + Span dst_span(0,0); + + for( ;cur_dst_lineleft.empty()); + const LinkArcItem &left_top = span->left.get_at(0); + + ASSERT(!span->right.empty()); + const LinkArcItem &right_top = span->right.get_at(0); + + ASSERT(cur_dst_line < left_top.dead_line); + ASSERT(cur_dst_line < right_top.dead_line); + + XY_POINT left, right; + int x = m_ellipse->get_left_arc_x(left_top.arc_center, cur_dst_line); + XY_POINT_SET(left, x, cur_dst_line); + x = m_ellipse->get_right_arc_x(right_top.arc_center, cur_dst_line); + XY_POINT_SET(right, x, cur_dst_line); + ASSERT(SPAN_LEFT(dst_span)<=left); + if ( SPAN_RIGHT(dst_span) >= left ) + { + if ( SPAN_RIGHT(dst_span)SPAN_LEFT(dst_span) ) + { + dst->push_back(dst_span); + SPAN_LEFT(dst_span) = left; + SPAN_RIGHT(dst_span) = right; + } + else + { + SPAN_LEFT(dst_span) = left; + SPAN_RIGHT(dst_span) = right; + } + + if (cur_dst_line+1==left_top.dead_line) + { + span->left.pop_front(); + } + if (cur_dst_line+1==right_top.dead_line) + { + span->right.pop_front(); + } + if (span->left.empty()) + { + ASSERT(span->right.empty()); + spans.RemoveAt(pos_cur); + pos_cur = pos_next; + span = &spans.GetNext(pos_next); + } + else + { + pos_cur = pos_next; + span = &spans.GetNext(pos_next); + } + } + } + if ( SPAN_RIGHT(dst_span)>SPAN_LEFT(dst_span) ) + { + dst->push_back(dst_span); + } +} + + +int gen_left_arc(int left_arc[], int rx, int ry) +{ + for (int y=-ry;y<=ry;y++) + { + left_arc[y+ry] = -(int)(0.5 + sqrt(float(ry*ry - y*y)) * float(rx)/float(ry)); + } + return 0; +} + +// +// XyEllipse +// + +XyEllipse::XyEllipse() + : m_left_arc(NULL) + , m_left_arc_base(NULL) + , m_cross_matrix(NULL) + , m_cross_matrix_base(NULL) + , m_rx(0), m_ry(0) +{ + +} + +XyEllipse::~XyEllipse() +{ + delete[]m_left_arc_base; + delete[]m_cross_matrix_base; +} + +/*** + * ry must >0 and rx must >=0 + ***/ +int XyEllipse::init( int rx, int ry ) +{ + if (rx<0 || ry<=0) + { + return -1; + } + m_left_arc_base = new int[2*ry+2]; + if (!m_left_arc_base) + { + return -1; + } + gen_left_arc(m_left_arc_base, rx, ry); + m_left_arc = m_left_arc_base + ry; + m_rx = rx; + m_ry = ry; + init_cross_point(); + return 0; +} + +int XyEllipse::get_left_arc_x( int y ) const +{ + return m_left_arc[y]; +} + +int XyEllipse::get_left_arc_x( XY_POINT center, int y ) const +{ + return XY_POINT_X(center) + m_left_arc[y-XY_POINT_Y(center)]; +} + +int XyEllipse::get_right_arc_x( int y ) const +{ + return -m_left_arc[y]; +} + +int XyEllipse::get_right_arc_x( XY_POINT center, int y ) const +{ + return XY_POINT_X(center) - m_left_arc[y-XY_POINT_Y(center)]; +} + +int XyEllipse::init_cross_point() +{ + if (m_rx<0 || m_ry<=0 ) + { + return 0; + } + m_cross_matrix_base = new int[ (2*m_ry+1)*(2*m_rx+1) ]; + if (!m_cross_matrix_base) + { + return -1; + } + + m_cross_matrix = m_cross_matrix_base + (2*m_ry)*(2*m_rx+1) + m_rx; + + + float f_rx = m_rx; + float f_ry = m_ry; + ASSERT(f_ry>0); + float rx_devide_ry = f_rx/f_ry; + float ry_2 = m_ry * m_ry; + + std::vector cross_x_base(2*m_ry+1+1); + int *cross_x = &cross_x_base[0] + m_ry + 1; + cross_x[-m_ry-1] = m_rx; + for (int dy=-2*m_ry;dy<=-1;dy++) + { + int y=-m_ry; + for ( ;y-dy<=m_ry;y++) + { + float f_cross_x = rx_devide_ry * ( sqrt(ry_2 - (y - dy)*(y - dy)) - sqrt(ry_2 - y*y) ); + cross_x[y] = ceil(f_cross_x); + ASSERT(cross_x[y]<=cross_x[y-1] && abs(cross_x[y])<=m_rx); + } + + int *cross_matrix = m_cross_matrix + dy*(2*m_rx+1); + + y--; + //[ -m_rx, cross_x[y] ) + for (int j=-m_rx;j-m_ry;y-- ) + { + //[ cross_x[y], cross_x[y-1] ) + for (int j=cross_x[y];j=-2*m_ry); + if (dx < -m_rx) + { + return MAX_CROSS_LINE; + } + else if (dx > m_rx) + { + return MIN_CROSS_LINE; + } + else // [-m_rx, m_rx] + { + ASSERT( abs( *(m_cross_matrix + dy*(2*m_rx+1) + dx) )<=m_ry || + *(m_cross_matrix + dy*(2*m_rx+1) + dx) == MIN_CROSS_LINE || + *(m_cross_matrix + dy*(2*m_rx+1) + dx) == MAX_CROSS_LINE ); + return *(m_cross_matrix + dy*(2*m_rx+1) + dx); + } +} + +int XyEllipse::cross_right( XY_POINT c1, XY_POINT base ) const +{ + int dx = XY_POINT_X(base) - XY_POINT_X(c1); + int dy = XY_POINT_Y(c1) - XY_POINT_Y(base); + ASSERT(dy<0 && dy>=-2*m_ry); + if (dx < -m_rx) + { + return MAX_CROSS_LINE; + } + else if (dx > m_rx) + { + return MIN_CROSS_LINE; + } + else // [-m_rx, m_rx] + { + ASSERT( abs( *(m_cross_matrix + dy*(2*m_rx+1) + dx) )<=m_ry || + *(m_cross_matrix + dy*(2*m_rx+1) + dx) == MIN_CROSS_LINE || + *(m_cross_matrix + dy*(2*m_rx+1) + dx) == MAX_CROSS_LINE ); + return *(m_cross_matrix + dy*(2*m_rx+1) + dx); + } +} diff --git a/src/subtitles/xy_widen_regoin.h b/src/subtitles/xy_widen_regoin.h new file mode 100644 index 0000000..3f50bda --- /dev/null +++ b/src/subtitles/xy_widen_regoin.h @@ -0,0 +1,21 @@ +#ifndef __XY_WIDEN_REGOIN_ECAEEA0A_9D51_4284_B0AE_081AF0E75438_H__ +#define __XY_WIDEN_REGOIN_ECAEEA0A_9D51_4284_B0AE_081AF0E75438_H__ + +class WidenRegionCreaterImpl; +class WidenRegionCreater +{ +public: + typedef tSpanBuffer SpanBuffer; + +public: + static WidenRegionCreater* GetDefaultWidenRegionCreater(); + + void xy_overlap_region(SpanBuffer* dst, const SpanBuffer& src, int rx, int ry); +private: + WidenRegionCreater(); + ~WidenRegionCreater(); + + WidenRegionCreaterImpl* m_impl; +}; + +#endif // __XY_WIDEN_REGOIN_ECAEEA0A_9D51_4284_B0AE_081AF0E75438_H__ \ No newline at end of file -- 2.11.4.GIT