frustrum clipping

[Flashesjetzt]

Hi hallo,

ich will eine simple Sache in 3D machen und das ohne Einsatz einer engine.


Ich hab das Problem mal im Anhang aufgezeichnet. Ich denke das ist etwas anschaulicher.


Es geht darum, dass Ebenen am viewing-Frustrum (Sichtfeld) der kamera geclippt werden, aber dadurch leerflächen im projektions-screen entstehen, wo sie eigentlich nicht sein sollten.
Kleines Beispiel: die Kamera befindet sich knapp über eine Ebene, die parellel zur z-Achse liegt. In positiver z-Richtung verschwindet diese Ebene im Fluchtpunkt. Der Teil der Ebene, der sich außerhalb des Sichtfeldes der Kamera befindet ( z.B. hinter der Kamera oder direkt unter der Kamera) muss geclippt werden. Ich berechne also den Schnittpunkt dieser Ebene mit dem Frustrum, damit ich nur den sichtbaren Bereich rendere.
In dem Fall schneidet die Ebene die near-clipping-plane.
Wenn die Ebene nun an dieser Stelle abgeschnitten wird, entsteht im Sichtfeld eine Freifläche, die doch nach meinem optischen Empfinden auch durch die Ebene gefüllt sein müßte.
Hmmm..., ich denke durch den Anhang wird das Problem noch etwas deutlicher.

Ein frustrum:

[Flashesjetzt]

Nochmal darüber nachgedacht. Es ist natürlich korrekt so. Wenn die Ebene auf mittlerer Höhe vor dem "Auge" liegt, kann man natürlich unter sie schauen. Man muss entsprechend dafür sorgen, dass man bestimmte Abstände einhält.

[Wakka]

Je näher sich die near plane an der kamera befindet, umso geringer/kleiner ist diese freie Fläche. Mit welchem Wert hast du denn die Plane bisher definiert?

[Flashesjetzt]

Hallo Wakka,

die plane hatte die Maße 800px X 600px und war 300px vor der kamera positioniert.
Mit diesen Werten spiele ich aber auch permanent rum.
Der Effekt mußte auftreten, da sich die Kamera in einem Gang befindet (der durch vier Ebenen begrenzt wird, rechts - links -oben - unten) der auch nur 800px hoch und 600px breit war.

Ich habe die Größe der plane sehr stark reduziert.
Nun tritt das Artefakt immer noch auf, aber es ist anderer Herkunft.
Wenn die berechnten clippingpoints auf unterschiedlichen Frustrumsbegrenzungsebenen sind, wird die Ecke, bzw. 2 Ecken einfach abgeschnitten. Ich habs nochmal aufgemalt (siehe Anhang).
Das muss man beim clippen oder später beim rendern irgendwie beachten. Zu dem Thema konnte ich bisher nichts finden im Internet.

[Wakka]

Hallo Flashesjetzt,

nach welcher Methode clippst du denn die Plane im Frustum, Sutherland-Hodgman? Ich habe jetzt nicht die Ahnung von den Möglichkeiten des nativen 3D, können Polygone mit mehr als vier Punkten definiert werden?

[Flashesjetzt]

Ja den Algorythmus benutze ich. Möglicherweise nicht ganz schulbuchmäßig, ich habe mir das aus 2-3 sourcecodes (Tutorial 4: Clipping , 3D Clipping to an arbitrary FOV - C++ Programming Tutorials, http://www.cubic.org/docs/3dclip.htm) zusammengeschustert.
Anschauliches applet: Cohen-Sutherland Clipping applet

Ich iteriere durch alle vertexe eines polygons und nehme zwei aufeinanderfolgende Eckpunkte: vertex 1 und vertex 2.
Ich berechne für beide vertexe alle Distanzen zu den Frustrumsebenen.

Liegen beide drinnen wird abgebrochen und der vertex 1 dem output-array hinzugefügt.

Liegen beide außerhalb wird geprüft, ob beide auf derselben Seite außerhalb liegen, wenn ja wird abgebrochen, wenn nein wird ähnlich verfahren wie im weiteren Fall.

Liegt vertex 1 im sichtbaren und vertex 2 im nicht sichtbaren Bereich, dann clippe ich nach und nach zur z-near eben zur linken und rechten Frustrumsebene und zuletzt zur Boden und Deckenebene des Frustrums. Falls geclippt wurde, berechne ich zwischendurch die Distanz zu den anderen Ebenen neu.

Ich habe in den oben verlinkten Beispielen, kein Hinweis gefunden, dass ein Polygon auf eine bestimme Anzahl von Ecken begrenzt ist. Ich weiss es nicht. Das Problem wird gar nicht angesprochen. Genauso wie das Problem, wenn die Kamera so nah an eine Ebene kommt, dass die Ebene zwar noch im Frustrum liegt, aber alle vertexe außerhalb des frustrums.

Das Problem tritt allerdings nur auf, wenn man sehr grosse Ebenen bzw. Polygone hat.

[Wakka]

Generell ist die Anzahl eines Polygons nicht begrenzt, auch nicht beim clipping. Wenn die Ebene im Frustum, die Vertices aber ausserhalb sind stellt dies fürs clipping auch kein Problem dar.

Liegt vertex 1 im sichtbaren und vertex 2 im nicht sichtbaren Bereich, dann clippe ich nach und nach zur z-near eben zur linken und rechten Frustrumsebene und zuletzt zur Boden und Deckenebene des Frustrums. Falls geclippt wurde, berechne ich zwischendurch die Distanz zu den anderen Ebenen neu.

was meinst du mit nach und nach zur z-near clippen? könntest du den Ablauf nochmal genauer erklären? vielleicht auch mal ein wenig code, kann nicht schaden

[Flashesjetzt]

Entschuldige, ich wollte damit sagen, dass ich nach und nach zu den frustrumsebenen clippe. Erst zur nearPlane, dann zu den Frustumsebenen links und rechts und dann zu Ebenen oben und unten.

Der code ist etwas redundant. Anstatt wie beim clipping-vorgang üblich, habe ich keine while-Schleife, die die flags überprüft.
Ich clippe erst zur nearplane (oder zplane, also die plane die alles abschneidet, was sich hinter ihr befindet.)
Falls geclippt wurde, berechne ich die Distanzen neu für den nächsten möglichen clipping-vorgang.


Hm naja, ist vermutlich nicht sonderlich gelungen.

PHP-Code:

private function clipPolygon(poly:IPolygon):void
        {
            var k1:int; 
            var k2:int;
            var outSideLeft:int = 1;
            var outSideRight:int = 2;
            var outSideUp:int = 4;
            var outSideDown:int = 8;
            var outSideBehind:int = 16;
            
            var vertices:Vector.<Vector3D> = poly.camVertices;
            var maxVertices:Number = vertices.length;
            
            var ii:int;
            var distRatio:Number;

            var tempVec1:Vector3D;
            var tempVec2:Vector3D;
            var tempVecs:Vector.<Vector3D> = new Vector.<Vector3D>();
        
            
            for (var i:int = 0; i < maxVertices; i++) 
            {
                k1 = 0;
                k2 = 0;
                
                ii = (i + 1) % maxVertices;
                tempVec1 = vertices[i].clone();
                tempVec2 = vertices[ii].clone();

        
                
                //alle Distanzen ausrechnen der Vektoren zu den FrustrumEbenen
                
                var distRight:Number =  MathUtils.distancePlaneVector(rightFrustrum.normalVec, rightFrustrum.distanceToOrigin, tempVec1);
                var distRight2:Number =  MathUtils.distancePlaneVector(rightFrustrum.normalVec, rightFrustrum.distanceToOrigin, tempVec2);
                              
                                var distLeft:Number =  MathUtils.distancePlaneVector(leftFrustrum.normalVec, leftFrustrum.distanceToOrigin, tempVec1);
                                var distLeft2:Number =  MathUtils.distancePlaneVector(leftFrustrum.normalVec, leftFrustrum.distanceToOrigin, tempVec2);
                
                var distTop:Number =  MathUtils.distancePlaneVector(topFrustrum.normalVec, topFrustrum.distanceToOrigin, tempVec1);
                var distTop2:Number =  MathUtils.distancePlaneVector(topFrustrum.normalVec, topFrustrum.distanceToOrigin, tempVec2);
                
                                var distBottom:Number = MathUtils.distancePlaneVector(bottomFrustrum.normalVec, bottomFrustrum.distanceToOrigin, tempVec1);
                var distBottom2:Number = MathUtils.distancePlaneVector(bottomFrustrum.normalVec, bottomFrustrum.distanceToOrigin, tempVec2);
                
                var distZPlane2:Number = MathUtils.distancePlaneVector(nearZPFrustrum.normalVec, nearZPFrustrum.distanceToOrigin, tempVec2);
                var distZPlane:Number = MathUtils.distancePlaneVector(nearZPFrustrum.normalVec, nearZPFrustrum.distanceToOrigin, tempVec1);
                
                
                // flags setzen falls Vektoren sich außerhalb der Ebene befinden
                if (distLeft < 0) k1 = outSideLeft;
                if (distRight < 0) k1 = outSideRight;
                if (distTop < 0) k1 |= outSideUp;
                if (distBottom < 0) k1 |= outSideDown;
                if (distZPlane < 0) k1 |= outSideBehind;
                
                if (distLeft2 < 0) k2 = outSideLeft;
                if (distRight2 < 0) k2 = outSideRight;
                if (distTop2 < 0) k2 |= outSideUp;
                if (distBottom2 < 0) k2 |= outSideDown;
                if (distZPlane2 < 0) k2 |= outSideBehind;
                
                
                
                
        
                
                // wenn beide Vektoren sich auf der gleichen Seite außerhalb des Frustrums befinden, kann abgebrochen werden, Linie muss nicht gerendert werden
                if (k1 & k2)
                {
                    trace ("gecancelt weil beide vektoren außerhalb sind");
                    continue;
                }
                

                //wenn beide Vektoren sich innerhalb des Frustrums befinden kann abgebrochen werden, vektoren müssen nicht neu berechnet werden
                if (!(k1 | k2))
                {
                    trace ("gecancelt weil beide vektoren drinnen sind");
                    tempVecs.push(tempVec1);
                    continue;
                }
                
                
                if (k1)
                {
                    
                    //checken ob sich vektor hinter der Kamera befindet    
                    if (distZPlane < 0)
                    {

                        distRatio = distZPlane2 / (distZPlane2 - distZPlane);

                        tempVec1.x = tempVec2.x + (tempVec1.x - tempVec2.x) * distRatio;
                        tempVec1.y = tempVec2.y + (tempVec1.y - tempVec2.y) * distRatio;
                        
                        tempVec1.z = tempVec2.z + (tempVec1.z - tempVec2.z ) * distRatio;
                        translation = true;
                        
                        
                        
                    }
                    
                    if (translation)
                    {
                        distLeft =  MathUtils.distancePlaneVector(leftFrustrum.normalVec, leftFrustrum.distanceToOrigin, tempVec1);
                
                        distRight =  MathUtils.distancePlaneVector(rightFrustrum.normalVec, rightFrustrum.distanceToOrigin, tempVec1);

                    }
                    
                    
                    //checken ob Vektor 1 sich links oder rechts außerhalb des Frustrums befindet und transalieren
                    if (distLeft < 0)
                    {
                    
                        distRatio =  distLeft2 / (distLeft2- distLeft);
    
                        tempVec1.x = tempVec2.x +(tempVec1.x - tempVec2.x) * distRatio;
                        tempVec1.y = tempVec2.y + (tempVec1.y - tempVec2.y) * distRatio;
                        tempVec1.z = tempVec2.z + (tempVec1.z - tempVec2.z ) * distRatio;
                        
                        translation = true;
                    }
                    
                    if (distRight < 0)
                    {
                        distRatio = distRight2 / (distRight2 - distRight);

                        tempVec1.x = tempVec2.x +(tempVec1.x - tempVec2.x) * distRatio;
                        tempVec1.y = tempVec2.y + (tempVec1.y - tempVec2.y) * distRatio;
                        tempVec1.z = tempVec2.z + (tempVec1.z - tempVec2.z ) * distRatio;
                        
                        translation = true;
                    }
                    
                    //wenn vektor transaliert wurde dann distanzen neu berechnen
                    if (translation)
                    {
                         distTop =  MathUtils.distancePlaneVector(topFrustrum.normalVec, topFrustrum.distanceToOrigin, tempVec1);
                         distBottom = MathUtils.distancePlaneVector(bottomFrustrum.normalVec, bottomFrustrum.distanceToOrigin, tempVec1);

                        translation = false;

                    }
                        
                    
                    //checken ob sich vektor über - oder unterhalb des frustrums befindet 
                    if (distTop < 0)
                    {
                        
                        distRatio = distTop2 / (distTop2 - distTop);
                        
                        tempVec1.x = tempVec2.x +(tempVec1.x - tempVec2.x) * distRatio;
                        tempVec1.y = tempVec2.y + (tempVec1.y - tempVec2.y) * distRatio;
                        tempVec1.z = tempVec2.z + (tempVec1.z - tempVec2.z ) * distRatio;
                        translation = true;
                        

                    }
                    
                    if (distBottom < 0)
                    {
                        
                        distRatio = distBottom2 / (distBottom2 - distBottom);
                        
                        tempVec1.x = tempVec2.x +(tempVec1.x - tempVec2.x) * distRatio;
                        tempVec1.y = tempVec2.y + (tempVec1.y - tempVec2.y) * distRatio;
                        tempVec1.z = tempVec2.z + (tempVec1.z - tempVec2.z ) * distRatio;
                        translation = true;
                        

                    }
                                
                    
                }
            
                
                
                //erster vektor wird immer gespeichert
                tempVecs.push(tempVec1);

                
                //Distanzen des neu berechneten Punktes berechnen
                distLeft =  MathUtils.distancePlaneVector(leftFrustrum.normalVec, leftFrustrum.distanceToOrigin, tempVec1);
                distRight =  MathUtils.distancePlaneVector(rightFrustrum.normalVec, rightFrustrum.distanceToOrigin, tempVec1);
                distTop =  MathUtils.distancePlaneVector(topFrustrum.normalVec, topFrustrum.distanceToOrigin, tempVec1);
                distBottom = MathUtils.distancePlaneVector(bottomFrustrum.normalVec, bottomFrustrum.distanceToOrigin, tempVec1);
                distZPlane = MathUtils.distancePlaneVector(nearZPFrustrum.normalVec, nearZPFrustrum.distanceToOrigin, tempVec1);
            
                
                if (k2)
                {
                    
                    //checken ob sich vektor hinter der Kamera befindet    
                    if (distZPlane2 < 0)
                    {
                        
                        distRatio = distZPlane / (distZPlane - distZPlane2);
                        //trace ("distRatioZ : " + distRatio);
                        tempVec2.x = tempVec1.x + (tempVec2.x - tempVec1.x) * distRatio;
                        tempVec2.y = tempVec1.y + (tempVec2.y - tempVec1.y) * distRatio;
                        tempVec2.z = tempVec1.z + (tempVec2.z - tempVec1.z ) * distRatio;
                        
                        translation = true;
                    }
                    
                    if (translation)
                    {

                         distLeft2 =  MathUtils.distancePlaneVector(leftFrustrum.normalVec, leftFrustrum.distanceToOrigin, tempVec2);
                         distRight2 =  MathUtils.distancePlaneVector(rightFrustrum.normalVec, rightFrustrum.distanceToOrigin, tempVec2);
                        
                        
                    }
                    

                    //checken ob Vektor 2 sich links oder rechts außerhalb des Frustrums befindet und transalieren
                    if (distLeft2 < 0)
                    {

                        distRatio =  distLeft / (distLeft- distLeft2);

                        tempVec2.x = tempVec1.x +(tempVec2.x - tempVec1.x) * distRatio;
                        tempVec2.y = tempVec1.y + (tempVec2.y - tempVec1.y) * distRatio;
                        tempVec2.z = tempVec1.z + (tempVec2.z - tempVec1.z ) * distRatio;
                        
                        translation = true;
                    }
                    
                    if (distRight2 < 0)
                    {
                        distRatio =  distRight / (distRight - distRight2);

                        tempVec2.x = tempVec1.x + (tempVec2.x - tempVec1.x) * distRatio;
                        tempVec2.y = tempVec1.y + (tempVec2.y - tempVec1.y) * distRatio;
                        tempVec2.z = tempVec1.z + (tempVec2.z - tempVec1.z ) * distRatio;
                        
                        translation = true;
                    }


                    if (translation)
                    {

                        distTop2 =  MathUtils.distancePlaneVector(topFrustrum.normalVec, topFrustrum.distanceToOrigin, tempVec2);
                        distBottom2 = MathUtils.distancePlaneVector(bottomFrustrum.normalVec, bottomFrustrum.distanceToOrigin, tempVec2);    
                        translation = false;
                    }
                        
                    
                    //checken ob sich vektor über - oder unterhalb des frustrums befindet 
                    if (distTop2 < 0)
                    {
                        
                        distRatio = distTop / (distTop - distTop2);
                        
                        tempVec2.x = tempVec1.x + (tempVec2.x - tempVec1.x) * distRatio;
                        tempVec2.y = tempVec1.y + (tempVec2.y - tempVec1.y) * distRatio;
                        tempVec2.z = tempVec1.z + (tempVec2.z - tempVec1.z ) * distRatio;
                        translation = true;
                    }
                    
                    if (distBottom2 < 0)
                    {
                        
                        distRatio = distBottom / (distBottom - distBottom2);
                        
                        tempVec2.x = tempVec1.x + (tempVec2.x - tempVec1.x) * distRatio;
                        tempVec2.y = tempVec1.y + (tempVec2.y - tempVec1.y) * distRatio;
                        tempVec2.z = tempVec1.z + (tempVec2.z - tempVec1.z ) * distRatio;
                        translation = true;
                    }
                    
                    
            
                    
                    
                    tempVecs.push(tempVec2);


                }
                
                trace ("vorläufiges ergebnis : " + tempVecs);
            
            }
            
            
            poly.camVertices = tempVecs;
            trace ("endergebnis : " + tempVecs);
            
            
        } 


[Flashesjetzt]

Zitat von Wakka

Hallo Flashesjetzt,

nach welcher Methode clippst du denn die Plane im Frustum, Sutherland-Hodgman? Ich habe jetzt nicht die Ahnung von den Möglichkeiten des nativen 3D, können Polygone mit mehr als vier Punkten definiert werden?

Ach, ich habe nach dem Cohen Sutherland Alogorithmus geclippt. Der Sutherland-Hodgman ist ja u.a. dazu gedacht um dieses Problem ein Polygon um die Ecke zu clippen, zu lösen. Na jetzt habe ich es, denke ich.

[Flashesjetzt]

So klappts:

PHP-Code:

private function clipPolygon(poly:IPolygon):void
        {
            
            var inPut:Vector.<Vector3D> = new Vector.<Vector3D>();
            var outPut:Vector.<Vector3D> = new Vector.<Vector3D>();
            
            
            
            inPut = inPut.concat(poly.camVertices);
            
            var vec1:Vector3D;
            var vec2:Vector3D;
            var clippedVec:Vector3D;
            var distRatio:Number;
            var ii:int;
            for each (var plane:Plane in frustrumPlanes) 
            {
                var numVecs:int = inPut.length;
                outPut = new Vector.<Vector3D>();
                for (var i:int = 0; i < numVecs; i++ ) 
                {
                    ii = (i + 1) % numVecs;
                    vec1 = inPut[i];
                    vec2 = inPut[ii];
                    
                    //trace ("vec1  ist : " + vec1);
                    //trace ("vec2  ist : " + vec2);
                    
                    var dist1:Number = MathUtils.distancePlaneVector(plane.normalVec, plane.distanceToOrigin, vec1);
                    var dist2:Number = MathUtils.distancePlaneVector(plane.normalVec, plane.distanceToOrigin, vec2);
                    
                    if (dist1 > 0 && dist2 > 0)
                    {
                        //falls beide innerhalb, vec2 ins array stecken und nächsten Schleifendurchgang starten
                        //trace ("beide drin");
                        outPut.push(vec2);
                        continue;
                    }
                    if (dist1 < 0 && dist2 < 0)
                    {
                        //falls beide außerhalb, nächsten Schleifendurchgang starten
                        //trace ("beide draussen");
                        continue;
                    }
                    
                    if (dist1 < 0)
                    {
                        distRatio = dist2 / (dist1 - dist2);
                        clippedVec = new Vector3D();
                        clippedVec.x = vec2.x  - (vec1.x - vec2.x ) * distRatio;
                        clippedVec.y = vec2.y - (vec1.y - vec2.y) * distRatio;
                        clippedVec.z = vec2.z - (vec1.z - vec2.z) * distRatio;
                        outPut.push(clippedVec);
                        outPut.push(vec2);
                        //trace (" vec2 liegt drinnen");
                        
                    }
                    else if (dist2 < 0)
                    {
                        distRatio = dist1 / (dist2 - dist1);
                        clippedVec = new Vector3D();
                        clippedVec.x = vec1.x - (vec2.x - vec1.x ) * distRatio;
                        clippedVec.y = vec1.y - (vec2.y - vec1.y ) * distRatio;
                        clippedVec.z = vec1.z - (vec2.z - vec1.z ) * distRatio;
                        outPut.push(clippedVec);
                        //trace ("vec 1 liegt drinnen");
                        
                    }
                    

                }
                

                
                inPut = outPut;
            
                
                
            }
            

            poly.camVertices = outPut;
}