Gabriele Cosmo
374 lines
10 KiB
Plaintext
374 lines
10 KiB
Plaintext
// Copyright (C) 2010, Guy Barrand. All rights reserved.
|
|
// See the file tools.license for terms.
|
|
|
|
#ifndef tools_zb_polygon
|
|
#define tools_zb_polygon
|
|
|
|
#include "edge_table"
|
|
#include "../mnmx"
|
|
|
|
namespace tools {
|
|
namespace zb {
|
|
|
|
class polygon {
|
|
|
|
static const int NUMPTSTOBUFFER = 200;
|
|
|
|
typedef struct _POINTBLOCK {
|
|
point pts[NUMPTSTOBUFFER];
|
|
struct _POINTBLOCK* next;
|
|
} POINTBLOCK;
|
|
|
|
int m_pETEn;
|
|
EdgeTableEntry* m_pETEs;
|
|
int m_numAllocPtBlocks;
|
|
POINTBLOCK m_FirstPtBlock;
|
|
public:
|
|
polygon():m_pETEn(0),m_pETEs(NULL),m_numAllocPtBlocks(0){}
|
|
virtual ~polygon(){clear();}
|
|
protected:
|
|
polygon(const polygon&){}
|
|
polygon& operator=(const polygon&){return *this;}
|
|
public:
|
|
void clear(){
|
|
POINTBLOCK* curPtBlock;
|
|
cmem_free(m_pETEs);
|
|
m_pETEn = 0;
|
|
for(curPtBlock = m_FirstPtBlock.next; --m_numAllocPtBlocks >= 0;){
|
|
POINTBLOCK* tmpPtBlock;
|
|
tmpPtBlock = curPtBlock->next;
|
|
cmem_free(curPtBlock);
|
|
curPtBlock = tmpPtBlock;
|
|
}
|
|
m_numAllocPtBlocks = 0;
|
|
}
|
|
|
|
typedef void (*scan_func)(void*,int,int,int);
|
|
|
|
void scan(int Count, /* number of pts */
|
|
const point* Pts, /* the pts */
|
|
int rule, /* winding rule */
|
|
scan_func a_proc,void* a_tag,
|
|
unsigned int a_width,unsigned int a_height){
|
|
// polytoregion
|
|
// Scan converts a polygon by returning a run-length
|
|
// encoding of the resultant bitmap -- the run-length
|
|
// encoding is in the form of an array of rectangles.
|
|
|
|
EdgeTableEntry* pAET; /* Active Edge Table */
|
|
int y; /* current scanline */
|
|
int iPts = 0; /* number of pts in buffer */
|
|
EdgeTableEntry* pWETE; /* Winding Edge Table Entry*/
|
|
ScanLineList* pSLL; /* current scanLineList */
|
|
|
|
EdgeTableEntry* pPrevAET; /* ptr to previous AET */
|
|
EdgeTable ET; /* header node for ET */
|
|
EdgeTableEntry AET; /* header node for AET */
|
|
ScanLineListBlock SLLBlock; /* header for scanlinelist */
|
|
int fixWAET = 0;
|
|
POINTBLOCK* curPtBlock;
|
|
int numFullPtBlocks = 0;
|
|
|
|
if(a_proc==NULL) return;
|
|
if(Count==0) return;
|
|
|
|
if(Count==3) {
|
|
point pts[3];
|
|
pts[0] = Pts[0];
|
|
pts[1] = Pts[1];
|
|
pts[2] = Pts[2];
|
|
|
|
point vp_down[3];
|
|
vp_down[0] = point(0,0,0);
|
|
vp_down[1] = point(a_width,0,0);
|
|
vp_down[2] = point(a_width,a_height,0);
|
|
if(triangles_overlap(pts,vp_down)) {
|
|
} else {
|
|
point vp_up[3];
|
|
vp_up[0] = point(0,0,0);
|
|
vp_up[1] = point(a_width,a_height,0);
|
|
vp_up[2] = point(0,a_height,0);
|
|
if(!triangles_overlap(pts,vp_up)) return;
|
|
}
|
|
}
|
|
|
|
int pts_xmin = Pts[0].x;
|
|
int pts_xmax = pts_xmin;
|
|
int pts_ymin = Pts[0].y;
|
|
int pts_ymax = pts_ymin;
|
|
{for(int count=1;count<Count;count++) {
|
|
if(Pts[count].x<pts_xmin) pts_xmin = Pts[count].x;
|
|
if(Pts[count].x>pts_xmax) pts_xmax = Pts[count].x;
|
|
if(Pts[count].y<pts_ymin) pts_ymin = Pts[count].y;
|
|
if(Pts[count].y>pts_ymax) pts_ymax = Pts[count].y;
|
|
}}
|
|
|
|
/* special case a rectangle */
|
|
point* pts = (point*)Pts;
|
|
if (((Count == 4) ||
|
|
((Count == 5) && (pts[4].x == pts[0].x) && (pts[4].y == pts[0].y))) &&
|
|
(((pts[0].y == pts[1].y) &&
|
|
(pts[1].x == pts[2].x) &&
|
|
(pts[2].y == pts[3].y) &&
|
|
(pts[3].x == pts[0].x)) ||
|
|
((pts[0].x == pts[1].x) &&
|
|
(pts[1].y == pts[2].y) &&
|
|
(pts[2].x == pts[3].x) &&
|
|
(pts[3].y == pts[0].y))))
|
|
{
|
|
int xmin,xmax,ymin,ymax;
|
|
xmin = (int)min_of(pts[0].x, pts[2].x);
|
|
ymin = (int)min_of(pts[0].y, pts[2].y);
|
|
xmax = (int)max_of(pts[0].x, pts[2].x);
|
|
ymax = (int)max_of(pts[0].y, pts[2].y);
|
|
if ((xmin != xmax) && (ymin != ymax))
|
|
{
|
|
for(y=ymin;y<=ymax;y++) a_proc(a_tag,xmin ,xmax ,y);
|
|
}
|
|
return;
|
|
}
|
|
|
|
if(Count>m_pETEn)
|
|
{
|
|
cmem_free(m_pETEs);
|
|
m_pETEn = Count;
|
|
m_pETEs = cmem_alloc<EdgeTableEntry>(m_pETEn);
|
|
if(m_pETEs==NULL)
|
|
{
|
|
m_pETEn = 0;
|
|
return;
|
|
}
|
|
}
|
|
|
|
ET.scanlines.next = (ScanLineList*)NULL;
|
|
ET.ymax = pts_ymin;
|
|
ET.ymin = pts_ymax;
|
|
|
|
AET.next = (EdgeTableEntry*)NULL;
|
|
AET.back = (EdgeTableEntry*)NULL;
|
|
AET.nextWETE = (EdgeTableEntry*)NULL;
|
|
AET.bres.minor_axis = pts_xmin;
|
|
|
|
SLLBlock.next = (ScanLineListBlock*)NULL;
|
|
|
|
CreateETandAET (Count,(point*)Pts, &ET, &AET, m_pETEs, &SLLBlock,pts_xmin,pts_ymin,pts_ymax);
|
|
|
|
pSLL = ET.scanlines.next;
|
|
|
|
curPtBlock = &m_FirstPtBlock;
|
|
pts = m_FirstPtBlock.pts;
|
|
|
|
|
|
if (rule==0)
|
|
{
|
|
/*
|
|
* for each scanline
|
|
*/
|
|
for (y = ET.ymin; y < ET.ymax; y++) {
|
|
/*
|
|
* Add a new edge to the active edge table when we
|
|
* get to the next edge.
|
|
*/
|
|
if (pSLL != NULL && y == pSLL->scanline)
|
|
{
|
|
LoadAET(&AET, pSLL->edgelist);
|
|
pSLL = pSLL->next;
|
|
}
|
|
pPrevAET = &AET;
|
|
pAET = AET.next;
|
|
|
|
/*
|
|
* for each active edge
|
|
*/
|
|
while (pAET) {
|
|
pts->x = pAET->bres.minor_axis;
|
|
pts->y = y;
|
|
pts++;
|
|
iPts++;
|
|
|
|
/*
|
|
* send out the buffer
|
|
*/
|
|
if (iPts == NUMPTSTOBUFFER)
|
|
{
|
|
if(numFullPtBlocks < m_numAllocPtBlocks)
|
|
{
|
|
curPtBlock = curPtBlock->next;
|
|
}
|
|
else
|
|
{
|
|
POINTBLOCK* tmpPtBlock = cmem_alloc<POINTBLOCK>(1);
|
|
if(tmpPtBlock==NULL)
|
|
{
|
|
FreeStorage(SLLBlock.next);
|
|
return;
|
|
}
|
|
tmpPtBlock->next = NULL; /*Barrand*/
|
|
curPtBlock->next = tmpPtBlock;
|
|
curPtBlock = tmpPtBlock;
|
|
m_numAllocPtBlocks++;
|
|
}
|
|
numFullPtBlocks++;
|
|
pts = curPtBlock->pts;
|
|
iPts = 0;
|
|
}
|
|
|
|
EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
|
|
}
|
|
(void) InsertAndSort(&AET);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
/*
|
|
* for each scanline
|
|
*/
|
|
for (y = ET.ymin; y < ET.ymax; y++) {
|
|
/*
|
|
* Add a new edge to the active edge table when we
|
|
* get to the next edge.
|
|
*/
|
|
if (pSLL != NULL && y == pSLL->scanline)
|
|
{
|
|
LoadAET(&AET, pSLL->edgelist);
|
|
ComputeWAET(&AET);
|
|
pSLL = pSLL->next;
|
|
}
|
|
pPrevAET = &AET;
|
|
pAET = AET.next;
|
|
pWETE = pAET;
|
|
|
|
/*
|
|
* for each active edge
|
|
*/
|
|
while (pAET) {
|
|
/*
|
|
* add to the buffer only those edges that
|
|
* are in the Winding active edge table.
|
|
*/
|
|
if (pWETE == pAET) {
|
|
pts->x = pAET->bres.minor_axis;
|
|
pts->y = y;
|
|
pts++;
|
|
iPts++;
|
|
|
|
/*
|
|
* send out the buffer
|
|
*/
|
|
if (iPts == NUMPTSTOBUFFER)
|
|
{
|
|
if(numFullPtBlocks < m_numAllocPtBlocks)
|
|
{
|
|
curPtBlock = curPtBlock->next;
|
|
}
|
|
else
|
|
{
|
|
POINTBLOCK* tmpPtBlock = cmem_alloc<POINTBLOCK>(1);
|
|
if(tmpPtBlock==NULL)
|
|
{
|
|
FreeStorage(SLLBlock.next);
|
|
return;
|
|
}
|
|
tmpPtBlock->next = NULL; /*Barrand*/
|
|
curPtBlock->next = tmpPtBlock;
|
|
curPtBlock = tmpPtBlock;
|
|
m_numAllocPtBlocks++;
|
|
}
|
|
numFullPtBlocks++;
|
|
pts = curPtBlock->pts;
|
|
iPts = 0;
|
|
}
|
|
pWETE = pWETE->nextWETE;
|
|
}
|
|
EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
|
|
}
|
|
|
|
/*
|
|
* recompute the winding active edge table if
|
|
* we just resorted or have exited an edge.
|
|
*/
|
|
if ( (InsertAndSort(&AET)!=0) || (fixWAET!=0) )
|
|
{
|
|
ComputeWAET(&AET);
|
|
fixWAET = 0;
|
|
}
|
|
}
|
|
}
|
|
FreeStorage (SLLBlock.next);
|
|
|
|
ScanPoints (numFullPtBlocks, iPts, &m_FirstPtBlock,a_proc,a_tag);
|
|
|
|
}
|
|
protected:
|
|
void ScanPoints (int numFullPtBlocks,
|
|
int iCurPtBlock,
|
|
POINTBLOCK* FirstPtBlock,
|
|
scan_func a_proc,void* a_tag) {
|
|
point* pts;
|
|
POINTBLOCK* CurPtBlock;
|
|
int i;
|
|
CurPtBlock = FirstPtBlock;
|
|
for ( ; numFullPtBlocks >= 0; numFullPtBlocks--)
|
|
{
|
|
/* the loop uses 2 points per iteration */
|
|
i = numFullPtBlocks!=0 ? NUMPTSTOBUFFER >> 1 : iCurPtBlock >> 1 ;
|
|
for (pts = CurPtBlock->pts; i--; pts += 2)
|
|
{
|
|
a_proc (a_tag,(int)(pts->x),(int)pts[1].x,(int)pts->y);
|
|
}
|
|
CurPtBlock = CurPtBlock->next;
|
|
}
|
|
}
|
|
|
|
// from: https://rosettacode.org/wiki/Determine_if_two_triangles_overlap#C++
|
|
static double det_2D(const point& a_p1,const point& a_p2,const point& a_p3) {
|
|
return a_p1.x*(a_p2.y-a_p3.y)+a_p2.x*(a_p3.y-a_p1.y)+a_p3.x*(a_p1.y-a_p2.y);
|
|
}
|
|
|
|
static void check_winding(point& a_p1,point& a_p2,point& a_p3) {
|
|
double detTri = det_2D(a_p1, a_p2, a_p3);
|
|
if(detTri < 0.0) { //swap p2 and p3:
|
|
point a = a_p3;
|
|
a_p3 = a_p2;
|
|
a_p2 = a;
|
|
}
|
|
}
|
|
|
|
static bool check_boundary_overlap(point& a_p1,point& a_p2,point& a_p3) {return det_2D(a_p1, a_p2, a_p3) < 0.0;}
|
|
|
|
static bool triangles_overlap(point* a_t1,point* a_t2) {
|
|
//Trangles must be expressed anti-clockwise
|
|
check_winding(a_t1[0], a_t1[1], a_t1[2]);
|
|
check_winding(a_t2[0], a_t2[1], a_t2[2]);
|
|
|
|
//For edge E of trangle 1,
|
|
for(int i=0; i<3; i++) {
|
|
int j=(i+1)%3;
|
|
|
|
//Check all points of trangle 2 lay on the external side of the edge E. If
|
|
//they do, the triangles do not overlap.
|
|
if (check_boundary_overlap(a_t1[i], a_t1[j], a_t2[0]) &&
|
|
check_boundary_overlap(a_t1[i], a_t1[j], a_t2[1]) &&
|
|
check_boundary_overlap(a_t1[i], a_t1[j], a_t2[2])) return false;
|
|
}
|
|
|
|
//For edge E of trangle 2,
|
|
for(int i=0; i<3; i++) {
|
|
int j=(i+1)%3;
|
|
|
|
//Check all points of trangle 1 lay on the external side of the edge E. If
|
|
//they do, the triangles do not overlap.
|
|
if (check_boundary_overlap(a_t2[i], a_t2[j], a_t1[0]) &&
|
|
check_boundary_overlap(a_t2[i], a_t2[j], a_t1[1]) &&
|
|
check_boundary_overlap(a_t2[i], a_t2[j], a_t1[2])) return false;
|
|
}
|
|
|
|
return true; //the triangles overlap.
|
|
}
|
|
|
|
};
|
|
|
|
}}
|
|
|
|
#endif
|