Ayuda Con Clipping

[Helius]

 Hola,

No a acabo de comprender por qué no me funciona bien mi procedimiento de clipping. Está basado en el código de flipcode sobre Sutherland-Hodgeman.

El caso es que necesito recortar los triángulos que sobresalgan por los lados de cada nodo de mi octree. Pues bien, para muchos triángulos me funciona perfectamente pero para otros (parece que son los que tienen que ser recortados por más de un plano) funciona mal.

Lo que hago es, por cada plano del nodo (6 en total, las caras del cubo), recorro todos los tris en su interior y los recorto con esta función:

Código [Seleccionar] Expand


inline bool MAT_TriangleClipping(stFileTri* pTri, PLANE* pPlane, stFileTri* pResult, int* iCount)
{
const float EPSILON = 0.01f;

bool allin=true;
bool allout=true;

float dist[3];

for (int h=0; h<3; h++)
{
 dist[h] = MAT_DistToPlane(pTri->pos[h], pPlane);
 if (dist[h] < -EPSILON) allin=false;
 if (dist[h] >= EPSILON) allout=false;
}
 
if (allin)
{
 iCount=0;
 return true;
}
else if (allout)
{
 iCount=0;
 return false;
}

stFileVertex lista[4];

bool clipped=false;
bool inside=(dist[0]>=0.0f);

int index=0;

for (int i=0; i<3; i++)
{
 stFileVertex v1, v2;

 v1.pos = pTri->pos[i];
 v1.normal = pTri->normal[i];
 v1.tex = pTri->tex[i];
 float dist1 = dist[i];

 float dist2;

 if (i==2)
 {
  v2.pos = pTri->pos[0];
  v2.normal = pTri->normal[0];
  v2.tex = pTri->tex[0];
  dist2 = dist[0];
 }
 else
 {
  v2.pos = pTri->pos[i+1];
  v2.normal = pTri->normal[i+1];
  v2.tex = pTri->tex[i+1];
  dist2 = dist[i+1];
 }

    if (inside && (dist2<-EPSILON)) ///--- going out
 {
  clipped=true;
  inside=false;
  float d = dist1 / (dist1 - dist2);
 
  stFileVertex inter;

  inter.pos.x = v1.pos.x + ((v2.pos.x - v1.pos.x) * d);
  inter.pos.y = v1.pos.y + ((v2.pos.y - v1.pos.y) * d);
  inter.pos.z = v1.pos.z + ((v2.pos.z - v1.pos.z) * d);

  inter.tex.x = v1.tex.x + ((v2.tex.x - v1.tex.x) * d);
  inter.tex.y = v1.tex.y + ((v2.tex.y - v1.tex.y) * d);

  MAT_Vector3Sumar(&v1.normal, &v2.normal, &inter.normal);
  MAT_Vector3Normalizar(&inter.normal);

  lista[index++]=inter;
 }
 else if (!inside && (dist2>=EPSILON)) ///--- coming in
 {
  clipped=inside=true;

  float d = dist1 / (dist1 - dist2);

  stFileVertex inter;

  inter.pos.x = v1.pos.x + ((v2.pos.x - v1.pos.x) * d);
  inter.pos.y = v1.pos.y + ((v2.pos.y - v1.pos.y) * d);
  inter.pos.z = v1.pos.z + ((v2.pos.z - v1.pos.z) * d);

  inter.tex.x = v1.tex.x + ((v2.tex.x - v1.tex.x) * d);
  inter.tex.y = v1.tex.y + ((v2.tex.y - v1.tex.y) * d);

  MAT_Vector3Sumar(&v1.normal, &v2.normal, &inter.normal);
  MAT_Vector3Normalizar(&inter.normal);
 
  lista[index++]=inter;
  lista[index++]=v2;
 }
 else if (inside && (dist2>=0.0f)) ///--- los dos dentro
 {
  lista[index++]=v2;
 }
}

if (!clipped)
{
 iCount=0;
 return true;
}
else if (index<3)
{
 iCount=0;
 return false;
}
else if (index==3)
{
 *iCount = 1;

 strcpy(pResult[0].material, pTri->material);
 
 for (int i=0; i<3; i++)
 {
  pResult[0].pos[i]=lista[i].pos;
  pResult[0].tex[i]=lista[i].tex;
  pResult[0].normal[i]=lista[i].normal;
 }
}
else if (index==4)
{
 *iCount = 2;
 strcpy(pResult[0].material, pTri->material);
 strcpy(pResult[1].material, pTri->material);

 for (int i=0; i<3; i++)
 {
  pResult[0].pos[i]=lista[i].pos;
  pResult[0].tex[i]=lista[i].tex;
  pResult[0].normal[i]=lista[i].normal;
 }

 pResult[1].pos[0]=lista[0].pos;
 pResult[1].pos[1]=lista[2].pos;
 pResult[1].pos[2]=lista[3].pos;

 pResult[1].tex[0]=lista[0].tex;
 pResult[1].tex[1]=lista[2].tex;
 pResult[1].tex[2]=lista[3].tex;

 pResult[1].normal[0]=lista[0].normal;
 pResult[1].normal[1]=lista[2].normal;
 pResult[1].normal[2]=lista[3].normal;
}

return true;
}


A ver si alguien me puede ayudar porque ya he probado todo y me siguen saliendo esos errores, aquí un ejemplo: http://www.geardome.com/files/hydra0001.jpg

Si os fijais sólo falla donde se cruzan varios planos, todos los tris que tienen que recortarse contra un único plano lo hacen bien, sólo hay que seguir las caras de los nodos para verlo.

Saludos.

PD: El triángulo que aparece más brillante es porque no se recorta bien y se solapa con otro y termina iluminándose dos veces con la misma luz.

[senior wapo]

 Solo he mirado el código por encima, pero no deberías inicializar inside con dist[2] en lugar de dist[0] ? O algo relacionado, me da a mi que el problema te viene de la variable inside.

[Helius]

 inside es booleana, dice si el punto 1 de la comprobación está del lado positivo o negativo del plano.

En la primera pasada tomo el vértice 0 del triángulo como punto 1 y el vértice 1 como punto 2.

En la siguiente pasada tomo el vértice 1 como el punto 1 y el 2 como punto 2 y en la tercera pasada se toma el vértice 2 como punto 1 y el 0 como punto 2.

De ahí que se inicialice a true o false según el primer vértice del tri este del lado positivo o negativo del plano.

¿Nadie ve algún error? Es extraño que para los polígonos que sólo se recortan contra un plano funcione bien :(

[Juan Mellado]

 Buffff....

Sin mirarlo mucho, lo único raro que veo son unos cuantos:

Código [Seleccionar] Expand


iCount=0;

que creo que deberían ser:

Código [Seleccionar] Expand


* iCount=0;


Saludos

[Helius]

 Sí, eso era un fallo, pero no me afectaba ya que la variable que paso por referencia la tenía inicializada a 0 y entonces funcionaba como cabría esperar. :(

El error debe estar en la lógica del clipping, ¿nadie utiliza Sutherland-Hodgeman o cualquier otra rutina de clipping en su motor?

Me siguen saliendo los mismos errores por más que lo reescribo, no se si estoy implementando bien el algoritmo  :blink:

Os pongo otra captura: http://www.geardome.com/files/hydra0002.jpg

[Helius]

 Aquí sigo depurando y he observado que aparentemente sólo ocurren fallos cuando hago varias pasadas, es decir cuando recorto contra más de un plano. Si recorto todos los tris contra un único plano me salen bien  :blink:

Aquí pongo el código que hace las llamadas en cada nodo, ya lo he revisado tantas veces que ya no veo nada:

Código [Seleccionar] Expand

float half = m_fWidth / 2.0f;

for(uint p = 0; p < 6; p++)
{
 PLANE plane;
 VECTOR3 point;

 if (p==0)
 { ///--- arriba

  point = m_vCenter;
  point.y += half;

  plane.a = 0.0f;
  plane.b = -1.0f;
  plane.c = 0.0f;
 }
 else if (p==1)
 { ///--- abajo

  point = m_vCenter;
  point.y -= half;

  plane.a = 0.0f;
  plane.b = 1.0f;
  plane.c = 0.0f;
 }
 else if (p==2)
 { ///--- derecha

  point = m_vCenter;
  point.x += half;

  plane.a = -1.0f;
  plane.b = 0.0f;
  plane.c = 0.0f;
 }
 else if (p==3)
 { ///--- izquierda

  point = m_vCenter;
  point.x -= half;

  plane.a = 1.0f;
  plane.b = 0.0f;
  plane.c = 0.0f;
 }
 else if (p==4)
 { ///--- alante

  point = m_vCenter;
  point.z += half;

  plane.a = 0.0f;
  plane.b = 0.0f;
  plane.c = -1.0f;
 }
 else if (p==5)
 { ///--- atrás

  point = m_vCenter;
  point.z -= half;

  plane.a = 0.0f;
  plane.b = 0.0f;
  plane.c = 1.0f;
 }

 plane.d = -((plane.a * point.x) + (plane.b * point.y) + (plane.c * point.z));

 stFileTri* pTempTri = theTempTriList.GetFirst();
 
 while (pTempTri)
 {
  stFileTri result[2];
  int vcount=0;
 
  ///--- ver si se sale pTempTri
  MAT_TriangleClipping(pTempTri, &plane, result, &vcount);

  ///--- si se sale
  if (vcount == 1)
  {
   ///--- si sólo es un tri cambiar el antiguo por el nuevo tri
   *pTempTri = result[0];
  }
  else if (vcount == 2)
  {
   ///--- si son 2 tris
   ///--- cambiar antiguo por el nuevo tri 0
   *pTempTri = result[0];
   ///--- añadir el nuevo tri 1
   theTempTriList.PushLast(result[1]);
  }

  pTempTri = theTempTriList.GetNext();
 }
}

[Helius]

 Necesito que alguien me eche una mano, no consigo entender porque el algoritmo funciona para los triángulos que sólo se recortan una vez y para aqullos que les hago varias pasadas con distintos planos fallan :(

Os pongo 3 nuevas capturas, se ve claramanete que en los triángulos que sólo se recortan contra un plano salen perfectos:
http://www.geardome.com/files/hydra0003.jpg
http://www.geardome.com/files/hydra0004.jpg
http://www.geardome.com/files/hydra0005.jpg

[Juan Mellado]

 ¿Por qué no pruebas con 1 triángulo sólo, de los que fallan, en vez de poner miles?

Me he copiado el código, me he inventado las estructuras que faltan, he hecho un par de ejemplos sencillos, y parece que funciona. Aunque he pasado de las normales, texturas y materiales, que creo que a lo sumo te estroperían la iluminación, color y tal, pero no la posición, que parece que es lo que te está pasando.

A ver si el error lo tienes en el GetFirst(), GetNext(), PushLast(), ....

No sé.

Te pongo el código (tú código) con el que he estado probando:

Código [Seleccionar] Expand


#include <windows.h>
#include <math.h>

struct VECTOR2{
    float x;
    float y;
   };

struct VECTOR3{
    float x;
    float y;
    float z;
   };

struct PLANE{
    float a;
    float b;
    float c;
    float d;
   };


struct stFileTri{
    VECTOR3 pos[3];
    VECTOR3 normal[3];
    VECTOR2 tex[3];
    char material[20];
   };

struct stFileVertex{
    VECTOR3 pos;
    VECTOR3 normal;
    VECTOR2 tex;
   };

struct TriList{

    stFileTri lista[100];
    int i;
    int max;

    TriList()
    {
       stFileTri st;

       i = 0;
       max = 0;

       st.material[0] =0;

       st.pos[0].x = -5;        //Vértices del triángulo a "testear"
       st.pos[0].y = 0;
       st.pos[0].z = 0;
       st.normal[0].x = 1;
       st.normal[0].y = 0;
       st.normal[0].z = 0;
       st.tex[0].x = 0;
       st.tex[0].y = 0;

       st.pos[1].x = 5;
       st.pos[1].y = 0;
       st.pos[1].z = 0;
       st.normal[1].x = 1;
       st.normal[1].y = 0;
       st.normal[1].z = 0;
       st.tex[1].x = 0;
       st.tex[1].y = 0;

       st.pos[2].x = 0;
       st.pos[2].y = 5;
       st.pos[2].z = 0;
       st.normal[2].x = 1;
       st.normal[2].y = 0;
       st.normal[2].z = 0;
       st.tex[2].x = 0;
       st.tex[2].y = 0;

       lista[max ++] = st;
    }

    stFileTri* GetFirst() { i = 0; return(&lista[i]); }
    stFileTri* GetNext() { ++ i; return( (i == max)? NULL: &lista[i]); }
    void PushLast(stFileTri tri) { lista[max ++] = tri; }

   };



float MAT_DistToPlane(VECTOR3 pos, PLANE * pPlane)
{
   return(pos.x * pPlane->a + pos.y * pPlane->b + pos.z * pPlane->c + pPlane->d);
}

void MAT_Vector3Sumar(VECTOR3 * v1, VECTOR3 * v2, VECTOR3 * result)
{
   result->x = v1->x + v2->x;
   result->y = v1->y + v2->y;
   result->z = v1->z + v2->z;
}

void MAT_Vector3Normalizar(VECTOR3 * v)
{
   float len = (float)sqrt(v->x * v->x + v->y * v->y + v->z * v->z);

    v->x = v->x / len;
    v->y = v->y / len;
    v->z = v->z / len;
}




TriList theTempTriList;
float m_fWidth = 1;
VECTOR3 m_vCenter = {0, 0, 0};   //Centrado en el origen y tamaño 1




inline bool MAT_TriangleClipping(stFileTri* pTri, PLANE* pPlane, stFileTri* pResult, int* iCount)
{
const float EPSILON = 0.01f;

bool allin=true;
bool allout=true;

float dist[3];

for (int h=0; h<3; h++)
{
dist[h] = MAT_DistToPlane(pTri->pos[h], pPlane);
if (dist[h] < -EPSILON) allin=false;
if (dist[h] >= EPSILON) allout=false;
}

if (allin)
{
iCount=0;
return true;
}
else if (allout)
{
iCount=0;
return false;
}

stFileVertex lista[4];

bool clipped=false;
bool inside=(dist[0]>=0.0f);

int index=0;

for (int i=0; i<3; i++)
{
stFileVertex v1, v2;

v1.pos = pTri->pos[i];
v1.normal = pTri->normal[i];
v1.tex = pTri->tex[i];
float dist1 = dist[i];

float dist2;

if (i==2)
{
 v2.pos = pTri->pos[0];
 v2.normal = pTri->normal[0];
 v2.tex = pTri->tex[0];
 dist2 = dist[0];
}
else
{
 v2.pos = pTri->pos[i+1];
 v2.normal = pTri->normal[i+1];
 v2.tex = pTri->tex[i+1];
 dist2 = dist[i+1];
}

   if (inside && (dist2<-EPSILON)) ///--- going out
{
 clipped=true;
 inside=false;
 float d = dist1 / (dist1 - dist2);

 stFileVertex inter;

 inter.pos.x = v1.pos.x + ((v2.pos.x - v1.pos.x) * d);
 inter.pos.y = v1.pos.y + ((v2.pos.y - v1.pos.y) * d);
 inter.pos.z = v1.pos.z + ((v2.pos.z - v1.pos.z) * d);

 inter.tex.x = v1.tex.x + ((v2.tex.x - v1.tex.x) * d);
 inter.tex.y = v1.tex.y + ((v2.tex.y - v1.tex.y) * d);

 MAT_Vector3Sumar(&v1.normal, &v2.normal, &inter.normal);
 MAT_Vector3Normalizar(&inter.normal);

 lista[index++]=inter;
}
else if (!inside && (dist2>=EPSILON)) ///--- coming in
{
 clipped=inside=true;

 float d = dist1 / (dist1 - dist2);

 stFileVertex inter;

 inter.pos.x = v1.pos.x + ((v2.pos.x - v1.pos.x) * d);
 inter.pos.y = v1.pos.y + ((v2.pos.y - v1.pos.y) * d);
 inter.pos.z = v1.pos.z + ((v2.pos.z - v1.pos.z) * d);

 inter.tex.x = v1.tex.x + ((v2.tex.x - v1.tex.x) * d);
 inter.tex.y = v1.tex.y + ((v2.tex.y - v1.tex.y) * d);

 MAT_Vector3Sumar(&v1.normal, &v2.normal, &inter.normal);
 MAT_Vector3Normalizar(&inter.normal);


 lista[index++]=inter;
 lista[index++]=v2;
}

else if (inside && (dist2>=0.0f)) ///--- los dos dentro
{
 lista[index++]=v2;
}
}

if (!clipped)
{
iCount=0;
return true;
}
else if (index<3)
{
iCount=0;
return false;
}
else if (index==3)
{
*iCount = 1;

strcpy(pResult[0].material, pTri->material);

for (int i=0; i<3; i++)
{
 pResult[0].pos[i]=lista[i].pos;
 pResult[0].tex[i]=lista[i].tex;
 pResult[0].normal[i]=lista[i].normal;
}
}
else if (index==4)
{
*iCount = 2;
strcpy(pResult[0].material, pTri->material);
strcpy(pResult[1].material, pTri->material);

for (int i=0; i<3; i++)
{
 pResult[0].pos[i]=lista[i].pos;
 pResult[0].tex[i]=lista[i].tex;
 pResult[0].normal[i]=lista[i].normal;
}

pResult[1].pos[0]=lista[0].pos;
pResult[1].pos[1]=lista[2].pos;
pResult[1].pos[2]=lista[3].pos;

pResult[1].tex[0]=lista[0].tex;
pResult[1].tex[1]=lista[2].tex;
pResult[1].tex[2]=lista[3].tex;

pResult[1].normal[0]=lista[0].normal;
pResult[1].normal[1]=lista[2].normal;
pResult[1].normal[2]=lista[3].normal;
}

return true;
}


void helius()
{
float half = m_fWidth / 2.0f;

for(int p = 0; p < 6; p++)
{
PLANE plane;
VECTOR3 point;

if (p==0)
{ ///--- arriba

 point = m_vCenter;
 point.y += half;

 plane.a = 0.0f;
 plane.b = -1.0f;
 plane.c = 0.0f;
}
else if (p==1)
{ ///--- abajo

 point = m_vCenter;
 point.y -= half;

 plane.a = 0.0f;

 plane.b = 1.0f;
 plane.c = 0.0f;
}
else if (p==2)
{ ///--- derecha

 point = m_vCenter;
 point.x += half;

 plane.a = -1.0f;
 plane.b = 0.0f;
 plane.c = 0.0f;
}
else if (p==3)
{ ///--- izquierda

 point = m_vCenter;
 point.x -= half;

 plane.a = 1.0f;
 plane.b = 0.0f;
 plane.c = 0.0f;
}
else if (p==4)
{ ///--- alante

 point = m_vCenter;
 point.z += half;

 plane.a = 0.0f;
 plane.b = 0.0f;
 plane.c = -1.0f;
}
else if (p==5)
{ ///--- atrás

 point = m_vCenter;
 point.z -= half;

 plane.a = 0.0f;
 plane.b = 0.0f;
 plane.c = 1.0f;
}

plane.d = -((plane.a * point.x) + (plane.b * point.y) + (plane.c * point.z));

stFileTri* pTempTri = theTempTriList.GetFirst();

while (pTempTri)
{
 stFileTri result[2];
 int vcount=0;

 ///--- ver si se sale pTempTri
 MAT_TriangleClipping(pTempTri, &plane, result, &vcount);

 ///--- si se sale
 if (vcount == 1)
 {
  ///--- si sólo es un tri cambiar el antiguo por el nuevo tri
  *pTempTri = result[0];
 }
 else if (vcount == 2)
 {
  ///--- si son 2 tris
  ///--- cambiar antiguo por el nuevo tri 0
  *pTempTri = result[0];
  ///--- añadir el nuevo tri 1
  theTempTriList.PushLast(result[1]);
 }

 pTempTri = theTempTriList.GetNext();
}
}
}


int WINAPI WinMain(HINSTANCE, HINSTANCE, LPSTR, int)
{
   helius();

   return(1);
}




Saludos

[Elvis Enmanuel]

 Casualmente en mi página http://www.dolphin-creations.125mb.com/
tienes un tutorial con código de como hacerlo tanto en 3d como en 2d, pero por si acaso aqui te pego el código en 3d.

Cuando recortas un polígono con más de un plano tienes que pasarle a la rutina de clipping los nuevos vertices que te
ha dejado tras el recorte, que pueden ser 3,4 o más. Yo almaceno cada recorte en una variable temporal donde se pueden
ir añadiendo vértices sin problemas. Observa la función clipPolygon().

Código [Seleccionar] Expand

/** Clips polygon against a plane */
Byte const CPolygonClipper::clipPolygonWithPlane(Byte nVerts,CPlane plane) {
Byte nout = 0;
Byte n1 = nVerts - 1;
SVert2d *clipA = (mClipIn+n1);
SVert2d *clipB = mClipIn;
float *distPtr = mClipDist;
/* We calculate distances only once */
for(Byte n2=0;n2<nVerts;n2++,distPtr++,clipB++) {
(*distPtr) = plane.distanceFromPoint( clipB->x,clipB->y );
}
/* Scan all polygon edges */
for(Byte n2=0;n2<nVerts;n2++) {
clipA = (mClipIn+n1);
clipB = (mClipIn+n2);
float distPtrA = *(mClipDist+n1);
float distPtrB = *(mClipDist+n2);
if (distPtrA<0.0f && distPtrB<0.0f) {
/* Edge is totally outside of the plane */
} else
if (distPtrA>=0.0f && distPtrB>=0.0f) {
/* Edge is totally inside of the plane */
*(mClipOut+nout) = *clipB;
nout++;
} else {
/* There is one vertex at each side */
*(mClipOut+(nout++)) = linearInterpolation(
*clipA,
*clipB,
-(distPtrA/(distPtrB-distPtrA)) /* delta */ );
/* The second vertex */
if (distPtrA < 0.0f && distPtrB >= 0.0f) {
*(mClipOut+(nout++)) = *clipB;
}
}
/* Go to the next position */
n1 = n2;
}
return nout;
}

/** Clips an entire polygon */
Byte const CPolygonClipper::clipPolygon(CPlane *plane,Byte nPlanes,Byte nVerts) {
for(Byte i=0;i<nPlanes;i++) {
nVerts = clipPolygonWithPlane(nVerts,plane[i]);
for(Byte v=0;v<nVerts;v++) {
*(mClipIn+v) = *(mClipOut+v);
}
}
mNumVertsResult = nVerts;
return nVerts;
}


[Helius]

 Me llega un poco tarde pero gracias!!  (ole)

La verdad es que lo solucioné, pero no me acuerdo como, jejeje.

Saludos.