Sutherland hodgman polygon clipping

[secp]

hallihallo

Ich hab die letzte woche damit verbracht den sh algorytmus in flash mx zu implementieren. Ein beispiel in flash hätte mir dabei sehr geholfen, sowas gibts aber glaube ich noch nicht. Deswegen stell ich jetzt hier her

Das ganze ist zwar für flash zu viel, überhaupt wegen der drawing api und so, naja vielleicht kanns trozdem mal wer brauchen.

greez

[bokel]

Sehr schön secp,

ich habe dein Script gleich mal um ein Draggen des
Dreiecks erweitert, damit man noch besser sieht,
um was es geht.

//Polygon zeichen funktion, übernimmt ein geschlossenes Polygon
function draw(pol, color, alpha) {
    lineStyle(0,color,alpha);
    beginFill(0xAAFFAA,100);
    moveTo(pol[0][0], pol[0][1]);
    for(i=1; i<pol.length;i++) {
        lineTo(pol[i][0], pol[i][1]);   
    }
    endFill();
}
 
//Das original polygon
orig_pol = new Array([0,-100], [200,100],[-100,100]);
 
//der bildschirmbereich
clipPlane = { x:0, y: 0, w:200, h:320 };
 
//ungeclipptes poly zeichnen :
draw(orig_pol, 0x00FF44, 100);
 
//bildschirm outlines zeichnen
moveTo(clipPlane.x,clipPlane.y); 
lineTo(clipPlane.w,clipPlane.y); 
lineTo(clipPlane.w,clipPlane.h); 
lineTo(clipPlane.x,clipPlane.h); 
lineTo(clipPlane.x,clipPlane.y);
 
//--------------------------Sutherland hodgman algorythmus------------------------------
 
//gibt true zurück falls der punkt xy im bildschirmbereich ist
function isVisible(x, y, kante, wert) {
    if(kante == "links") {
        return x >= wert;
    }else if(kante == "rechts"){
        return x <= wert;
    }else if(kante == "oben") {
        return y >= wert;
    }else if(kante == "unten") {
        return y <= wert;
    }   
}
 
//berechnet den schnittpunkt wenn ein punkt der linie außerhalb des bildschirmbereichs liegt
function intersection(x1,y1, x2, y2, kante, wert) {
    var a = isVisible(x1, y1, kante, wert);
    var b = isVisible(x2, y2, kante, wert);
    if((a && b ) or (!a && !b) ) {
        return 0;   
    }else{
        var slope =(y2 - y1) / (x2 - x1);
        if(kante == "links" or kante == "rechts") {
            arr = new Array(wert, ((wert-x1) * slope)+y1);
            return arr;
        }else{
            arr = new Array( ((wert-y1) / slope)+x1, wert);
            return arr;
        }
    }
}
 
//gibt ein neues, geclipptes poly zurück.
//muß für jede bildschirmkante aufgerufen werden
function clipPoly( poly, kante, wert) {
    sh_pol = new Array();
    var sx, sy, inter, np;
    np=-1;
    poly[poly.length]= new Array(poly[0][0], poly[0][1]);
    for( var i=1; i<poly.length; i++) {
        sx = poly[i-1][0]; 
        sy = poly[i-1][1];
        if(isVisible(sx, sy, kante, wert)) {
                np++;
                sh_pol[np] = new Array(sx, sy);
         }
         inter = _root.intersection(sx,sy, poly[i][0], poly[i][1], kante, wert);
         if(inter != 0) {
                np++;
                sh_pol[np] = new Array(inter[0], inter[1]);
         }
    }
    return sh_pol;
}
//-----------------------------------------------------------------------------------
 
//Anwendung auf das original polygon:
newPol = clipPoly(orig_pol, "links", clipPlane.x);
newPol = clipPoly(newPol, "oben", clipPlane.y);
 
//geclipptes poly zeichnen
draw(newPol,0x0044FF, 80);
 
function doDrag(){
    var xDif = _xmouse - xStart;
    var yDif = _ymouse - yStart;
    var newPol = [];
    for(var i in orig_pol){
          newPol[i] = [];
          newPol[i][0] = orig_pol[i][0] + xDif;
          newPol[i][1] = orig_pol[i][1] + yDif;
    }
    clear();
 
    //ungeclipptes poly zeichnen :
    draw(newPol, 0x00FF44, 100);
    
    //bildschirm outlines zeichnen
    moveTo(clipPlane.x,clipPlane.y); 
    lineTo(clipPlane.w,clipPlane.y); 
    lineTo(clipPlane.w,clipPlane.h); 
    lineTo(clipPlane.x,clipPlane.h); 
    lineTo(clipPlane.x,clipPlane.y);
    
    newPol = clipPoly(newPol, "links", clipPlane.x);
    newPol = clipPoly(newPol, "oben", clipPlane.y);
    newPol = clipPoly(newPol, "rechts", clipPlane.x + clipPlane.w);
    newPol = clipPoly(newPol, "unten", clipPlane.y + clipPlane.h);
 
    draw(newPol,0x0044FF, 80);
}
 
onMouseDown  = function(){
    xStart = _xmouse;
    yStart = _ymouse;
    onEnterFrame = doDrag;
}
 
onMouseUp = function(){
    delete onEnterFrame;
} 

btw. im neuen Powerflasherbuch gibt es auch einen
Abschnitt darüber.

mfg r.

[secp]

wow

und gegen alle kanten. dann würde ich dir meine aufgespeedete variante vorschlagen:

array.prototype.clipPolyH = function(wert) {
	var sh_pol = new Array();
	var np=-1;
	this[this.length] = [this[0][0], this[0][1]];
	for( var i=1; i<this.length; i++) {
		if(this[i-1][1] <= wert) {
				sh_pol[++np] = [this[i-1][0], this[i-1][1]];
		 }
		 if((this[i-1][1] <= wert) != (this[i][1] <= wert)) {
			  sh_pol[++np] = [ ((wert-this[i-1][1]) / ((this[i][1] - this[i-1][1]) / (this[i][0] - this[i-1][0]))) + this[i-1][0], wert ];
		 }
	}
	return sh_pol;
}

array.prototype.clipPolyX = function(wert) {
	var sh_pol = new Array();
	var np=-1;
	this[this.length] = [this[0][0], this[0][1]];
	for( var i=1; i<this.length; i++) {
		if(this[i-1][0] >= wert) {
				sh_pol[++np] = [this[i-1][0], this[i-1][1]];
		 }
		if(( this[i-1][0] >= wert) != (this[i][0] >= wert)) {
			sh_pol[++np] =[wert, ((wert-this[i-1][0]) * ((this[i][1] - this[i-1][1]) / (this[i][0] - this[i-1][0]))) + this[i-1][1]];
		}
	}
	return sh_pol;
}
array.prototype.clipPolyW = function(wert) {
	var sh_pol = new Array();
	np=-1;
	this[this.length] = [this[0][0], this[0][1]];
	for( var i=1; i<this.length; i++) {
		if(this[i-1][0] <= wert) {
				sh_pol[++np] = [this[i-1][0], this[i-1][1]];
		 }
		if((this[i-1][0] <= wert) != (this[i][0] <= wert)) {
			sh_pol[++np] = [wert, ((wert-this[i-1][0]) * ((this[i][1] - this[i-1][1]) / (this[i][0] - this[i-1][0]))) + this[i-1][1]];
		}
	}
	return sh_pol;
}
array.prototype.clipPolyY = function(wert) {
	var sh_pol = new Array();
	np=-1;
	this[this.length] = [this[0][0], this[0][1]];
	for( var i=1; i<this.length; i++) {
		if(this[i-1][1] >= wert) {
				sh_pol[++np] = [this[i-1][0], this[i-1][1]];
		 }
		if((this[i-1][1] >= wert) != (this[i][1] >= wert)) {
			sh_pol[++np] = [ ((wert-this[i-1][1]) / ((this[i][1] - this[i-1][1]) / (this[i][0] - this[i-1][0]))) + this[i-1][0], wert ];
		}
	}
	return sh_pol;
}

[secp]

Hmm mit den array protos geht dann der for in loop nicht mehr.

Außerdem würde ich gerne das array direkt bearbeiten. Hättest du dafür eine lösung? Immer wenn ich das probiere k***t meine kiste ab

[bokel]

Wenn du was probierst ? Hast du ein Beispiel ?

Btw. ich würde auf das zweidimensionale Array
verzichten und die x und y werte einfach
hintereinander in ein normales Array schreiben.

mfg r.

[Gnut]

hauptgrund: mehrdimensional = mehr performance-verlust (AS)
das hab ich vorallem bei der 3d-geschichte eindeutig bemerkt...

[secp]

ich habs jetzt auc h´auf 1dim umgestellt, jetzt würde ich gerne keine arrays hin und herschieben müssen, das schaff ich aber nicht - vielleciht geht das gar nicht? hier mal ein versuch :

array.prototype.clipPolyX = function(wert) {
    var sh_pol = new Array();
    var sx, sy, np, slope;
    np=-1;
    this[this.length] = this[0]
    this[this.length] = this[1];
    for( var i=2; i<this.length; i+=2) {
        sx = this[i-2];
        sy = this[i-1];
        if(sx >= wert) {
                sh_pol[++np]=sx;
                sh_pol[++np]=sy;
         }
        if(( sx >= wert) != (this[i] >= wert) ) {
            slope = (this[i+1] - sy) / (this[i] - sx);
            sh_pol[++np] = wert;
            sh_pol[++np] = ((wert-sx) * slope) + sy;
        }
    }
    return sh_pol;
}
 
array.prototype.clipPolyY = function(wert) {
    //var sh_pol = new Array();
    var sx, sy, np, slope;
    np=-1;
    this[this.length] = this[0]; 
    this[this.length] = this[1];
    for( var i=2; i<this.length; i+=2) {
        sx = this[i-2]; 
        sy = this[i-1];
        if(sy >= wert) {
                //sh_pol[++np] = sx;
                //sh_pol[++np] = sy;
         }else{
                this.splice(i,2);
                i-=2;
         }
        if(( sy >= wert) != (this[i+1] >= wert) ) {
            slope = (this[i+1] - sy) / (this[i] - sx);
            this.splice(i,1,((wert-sy) / slope) + sx);
            this.splice(i+1,1, wert);
            i+=2;
        }
    }
    //return sh_pol;
}
 
 
//Polygon zeichen funktion, übernimmt ein geschlossenes Polygon
function draw(pol, color, alpha) {
    lineStyle(0,color,alpha);
    beginFill(color,alpha);
    moveTo(pol[0], pol[1]);
    for(i=2; i<pol.length;i+=2) {
        lineTo(pol[i], pol[i+1]);   
    }
    endFill();
}
 
 
 
 
 
//Das original polygon
orig_pol = new Array(0,-100, 
                     100,100,
                     -100,100);
 
//der bildschirmbereich
clipPlane = { x:0, y: 0, w:200, h:320 };
 
//ungeclipptes poly zeichnen :
draw(orig_pol, 0x00FF44, 100);
 
//bildschirm outlines zeichnen
moveTo(clipPlane.x,clipPlane.y); lineTo(clipPlane.w,clipPlane.y); lineTo(clipPlane.w,clipPlane.h); lineTo(clipPlane.x,clipPlane.h); lineTo(clipPlane.x,clipPlane.y);
 
 
 
 
//Anwendung auf das original polygon:
newPol = orig_pol.clipPolyX(clipPlane.x);
newPol.clipPolyY(clipPlane.y);
 
//geclipptes poly zeichnen
draw(newPol,0x000033, 50); 

der clipPolyX prototyp funzt wie vorher, nur 1dim.

Beim yClip hab ich das probiert, das das array direkt bearb. wird. Ich check da aber irgendwas nicht . Wahrscheinlich muß ich da irgendwas tmp´n. Das ist mir irgendwie zu hoch

[bokel]

Schau dir mal die Doku von array.splice an,
dann klappt es auch

Ich glaube aber nicht, dass das was bringt,
es wird eher langsamer.

push ist übrigens auch schneller als a[a.length]=b,
zumindest seit dem neuen 6er Plugin.

t = getTimer();
 
a = [];
for(i=0;i<1000;i++){
    a.push(i);
}
trace(getTimer() - t);
 
t = getTimer();
 
a = [];
for(i=0;i<1000;i++){
    a[a.length] = i;
}
trace(getTimer() - t);
 
t = getTimer();
 
a = [];
for(i=0;i<1000;i++){
    a[i] = i;
}
trace(getTimer() - t); 

Hier ist eine optimierte Version von clipPolyX

//gibt ein neues, geclipptes poly zurück.
function clipPolyX(poly, wert) {
    var sh_pol = new Array();
    var x1, y1, x2, y2;
    var a, j;
 
    poly.push(x1=poly[0]);
    poly.push(y1=poly[1]);
    
    j = poly.length-2;
    a = (x1 >= wert);
    
    while(j > 0){
        // koordinaten kommen umgekehrt
        y2 = poly[--j];
        x2 = poly[--j];
        //    
        if (a) {
            sh_pol.push(x1);
            sh_pol.push(y1);
        }
        //
        //schnittpunkt berechnen
        if(a != (x2 >= wert)){
            sh_pol.push(wert);
            sh_pol.push((wert - x1) * (y2 - y1) / (x2 - x1) + y1);
            a = !a;
        }
        //
        x1 = x2;
        y1 = y2;
    }
    return sh_pol;
} 

mfg r.

[secp]

hmm ,da sind meine array protos mit 2 dimensionen ja genauso schnell. Ich glaub schon das das sh_pol array viel zeit benötigt, das wird ja dann by value zurückgegeben, oder? by ref? naja pointer wären cool .

Das splice ist nicht das prob, sondern der algo.

[bokel]

Wie hast du denn gemessen ?
Ich bekomme die folgenden Ergebnisse:

3286 clipPolyX eindimensional bokel
3977 Array.clipPolyX eindimensional secp
4445 Array.clipPolyX zweidimensional secp

x = 10;
xHalbe = 5;
loops = 200;
 
//array mit abwechselnd grossen und 
//kleinen wertepärchen erzeugen
a = [];
for(i=0; i<x; i++){
    a.push(i);
    a.push(i);
    a.push(x-i);
    a.push(x-i);
}
 
//wie oben nur zweidimensional
a2 = [];
for(i=0; i<x; i++){
    a2.push([i, i]);
    a2.push([x-i, x-i]);
}
 
//bokel eindimensional
t = getTimer();
b = a.slice(0);
for(i=0;i<loops; i++){
    clipPolyX(b, xHalbe);   
}
trace(getTimer() - t);
 
//secp eindimensional
t = getTimer();
b = a.slice(0);
for(i=0;i<loops; i++){
    b.clipPolyX(xHalbe);    
}
trace(getTimer() - t);
 
//secp zweidimensional
t = getTimer();
b = a2.slice(0);
for(i=0;i<loops; i++){
    b.clipPolyX2(xHalbe);   
}
trace(getTimer() - t); 

Arrays werden by reference übergeben.

mfg r.

[secp]

ja lol, welche funktoinen hast du da verwendet? mein 2. post sind die 2dimensionalen

[bokel]

ja,
genau die habe ich benutzt

mfg r.

[secp]

acbso, dann muß ich mir dein funktionchen ma l genauer anschauen. Warum wird denn das schneller?

[secp]

hmm. ich hab das jetzt mal getestet. dabei ist mir wiedermal aufgefallen das das testen nichts bringt! hier mein test ergebnis:

//Polygon zeichen funktion, übernimmt ein geschlossenes Polygon
function draw(pol, color, alpha) {
        lineStyle(0,color,alpha);
        beginFill(color,alpha);
        moveTo(pol[0], pol[1]);
        for(i=2; i<pol.length;i+=2) {
                lineTo(pol[i], pol[i+1]);
        }
        endFill();
}
array.prototype.clipPolyX1Dim = function(wert) {
	var sh_pol = new Array();
	var np=-1;
	this.push(this[0]);
	this.push(this[1]);
	for( var i=2; i<this.length; i+=2) {
		if(this[i-2] >= wert) {
				sh_pol[++np]=this[i-2];
				sh_pol[++np]=this[i-1];
		 }
		if(( this[i-2] >= wert) != (this[i] >= wert) ) {
			sh_pol[++np] = wert;
			sh_pol[++np] = ((wert-this[i-2]) * ((this[i+1] - this[i-1]) / (this[i] - this[i-2]))) + this[i-1];
		}
	}
	return sh_pol;
}

//bokels
//gibt ein neues, geclipptes poly zurück.
function clipPolyX_bokel(poly, wert) {
        var sh_pol = new Array();
        var x1, y1, x2, y2;
        var a, j;
        
        poly.push(x1=poly[0]);
        poly.push(y1=poly[1]);
        
        j = poly.length-2;
        a = (x1 >= wert);
        
        while(j > 0){
                // koordinaten kommen umgekehrt
                y2 = poly[--j];
                x2 = poly[--j];
                //
                if (a) {
                        sh_pol.push(x1);
                        sh_pol.push(y1);
                }
                //
                //schnittpunkt berechnen
                if(a != (x2 >= wert)){
                        sh_pol.push(wert);
                        sh_pol.push((wert - x1) * (y2 - y1) / (x2 - x1) + y1);
                        a = !a;
                }
                //
                x1 = x2;
                y1 = y2;
        }
        return sh_pol;
}


//Das original polygon
orig_pol = new Array(0,-100,
                    100,100,
                   -100,100);
max = 50;
/// erster Aufruf immer schneller !!
t = getTimer();
for(i=0; i< max; i++) newPolmy = orig_pol.clipPolyX1Dim(0);
trace("1Dim : " + (getTimer() - t));

//zweiter immer langsamer!!
t = getTimer();
for(i=0; i< max; i++) newPol_bokel= clipPolyX_bokel(orig_pol, 0);
trace("bokels: " + (getTimer() - t));

hier kommt dann das raus:

1Dim : 271
bokels: 599


Allerdings wenn ich als erstes deine func ausführe ist deine schneller, und meine 3mal so langsan. Was soll das?

[bokel]

Möglicherweise liegt es daran, dass das originale Array
immer laenger wird, und meine Methode dann sozusagen
unter erschwerten Bedingungen ablaeuft.



Versuch es mal so:
(das Array wird jedesmal neu kopiert.)

//Das original polygon
ar = new Array(0,-100,
                    100,100,
                   -100,100);
max = 150;
/// erster Aufruf immer schneller !!
t = getTimer();
orig_pol = ar.slice(0);
for(i=0; i< max; i++) newPolmy = orig_pol.clipPolyX1Dim(0);
trace("1Dim : " + (getTimer() - t));
 
//zweiter immer langsamer!!
t = getTimer();
orig_pol = ar.slice(0);
for(i=0; i< max; i++) newPol_bokel= clipPolyX_bokel(orig_pol, 0);
trace("bokels: " + (getTimer() - t)); 

mfg r.