Identifisering
Grafikk
Børre Stenseth
Forklaring av>Identifikasjon

Å identifisere ved å peke

Hva

Problemstillingen vi reiser er den at vi ønsker å identifisere en del av scenen ved å peke og klikke på den med mus. Det er lett å overbevise seg om at dette er en langt mer komplisert operasjon i rommet enn det er i planet.

Vi kikker litt på problemstillingen i planet først.

ringer

I planet

I planet vil en slik identifisering generelt foregå ved å gjøre tester av et punkt mot polygoner. Ofte er problemstillingen slik at vi kan forenkle situasjonen til til innsidetester i rektangler.

planhit

Følgende to rutiner er en skisse på en inside test. Den første rutina, Intersection, finner eventuelle skjæringer mellom linjestykker og kan brukes generelt til dette formålet.

BOOL Intersection(
          CPoint&p1,CPoint& p2,
          CPoint&p3,CPoint& p4,
          CPoint&ps)
{

  /* finds the intersecton between lines p1-p2 and p3-p4
     return TRUE if intersection, FALSE else
     result in ps, if intersection
     use parametric equations for the lines
  */
  int dx1=p2.x-p1.x;
  int dx2=p4.x-p3.x;
  int dy1=p2.y-p1.y;
  int dy2=p4.y-p3.y;
  int n=dx2*dy1-dy2*dx1;

  if(n==0) return FALSE;
  double s=1.0*(dx1*(p3.y-p1.y)-dy1*(p3.x-p1.x))/(1.0*n);
  if ((s<0.0)||(s>1.0)) return FALSE;
  double t=1.0*(dx2*(p3.y-p1.y)-dy2*(p3.x-p1.x))/(1.0*n);
  if((t<0.0)||(t>1.0)) return FALSE;

  ps.x=(int)(dx1*t+p1.x);
  ps.y=(int)(dy1*t+p1.y);
  return TRUE;
}

Den andre rutina, Inside, bruker Intersection til å teste om et punkt er inne i et polygon. Det finnes mange andre måter å gjøre dette på.

BOOL Inside(CPoint p)
{
  /* Have we hit the polygon in pointarray POL ?
     assume POL closed, POL [0]== POL [POL.GetSize()-1]
     if we have a sorrounding box for the polygon
     we should test this first
     For instance like this:
      if(!m_BigR.PtInRect(p))
            return FALSE;
  */

  // Count intersections to the left of p
  // odd is hit, even is miss
  int pix;
  CPoint p1,p2,p3,p4,ps;
  BOOL Inside=FALSE;

  p1.x=-<a number smaller than smallest x in POL >;
  p1.y=p.y;
  p2.x=<a number greater than greatest x in POL >;
  p2.y=p.y;
  for(pix=0;pix< POL.GetSize()-1;pix++)
  {
    p3= POL [pix];
    p4= POL [pix+1];
    if(Intersection(p1,p2,p3,p4,ps))
      if (ps.x < p.x )
        Inside=!Inside;
  }
  return Inside;
}

Begge disse rutinene, sammen med andre rutiner for plangeometri, er drøftet i modulen Algoritmer, Det er også laget et demonstrasjonsprogram for å eksperimentere med identifisering i planet, se referanser i den nevnte modulen.

En mulig kompliserende faktor ved slik identifikasjon i planet er transformasjoner fra verdenskoordinater(logical coordinates) til skjermkoordinater (device coordinates). Slik transformasjon er drøftet i en egen modul og vi vet at i vanlig Windows-programmering har vi støtte for den inverse transformasjon slik at vi kan ta et skjermpunkt, transformere det til verdenskoordinater og eventuelt gjennomføre innsidetesten i modell- eller verdenskoordinater. Minner om rutina: DPtoLP() i MS_Windows, eventuelt CDC:DPtoLP(). (Device Point to Logical Point) dersom vi bruker MFC.

Vi kan resonnere relativt enkelt i planet selv om vi tenker oss ytterligere transformasjoner. Vi kan tenke oss en grafisk pakke med rotasjoner, translasjoner og skaleringer i planet. Den sammensatte transformasjonsmatrisen kan inverteres og vi kan regne oss tilbake fra skjermen til modellen før treff-testing.

I rommet

I 3D blir slike resonnementer vanskeligere. I prinsipp skyldes dette to forhold:

  • Scenebeskrivelsen skal transformeres til et Viewkoordinatsystem. Dette lar seg prinsipielt løse ved en invers-transformasjon.
  • Vi har problemer med å holde styr på hvilke figurer som ligger nærmest øye. Vi må hele tiden ta høyde for det faktum at en figur eller del av figur kan komme foran en annen figur eller del av en annen figur. Vi kan på forhånd vanskelig generalisere denne problemstillingen slik at vi på den ene siden kan la brukeren fritt velge synsvinkel og samtidig holde styr på hva som skjuler hva, sett fra brukerens (pekerens) synspunkt.

I OpenGL er denne problemstillingen løst ved en metode som griper inn i selve renderingstrategien. Vi kan kort beskrive strategien slik:

  1. Brukeren klikker
  2. Vi (programmet) setter opp et smalt klippevolum med senter i museklikket.
  3. Programmet gjentar de delene av uttegningen som er nødvendig for å identifisere hvilke deler av scenen som vil være synlig i den smale klippevolumet. Dette skjer uten at scenen rendres til skjermen.
  4. Under denne ekstra "uttegningen" kan vi navngi sceneelementer. De som er kandidater til visning noters fortløpende av OpenGL i en egen liste.
  5. Vi kan etter den ekstra "uttegningen" lese listen og se hvilke objekter som ville ha blitt helt eller delvis tegnet ut ved den kunstige klippepyramiden. Her kan vi lese de aktuelle navnene og vi kan lese z-koordinaten i Viewsystemet.

C++ - programmet HitMe, se referanser, illustrerer en enkel identifikasjon av en en smultring i en en ring med smultringer (toruser).

De interessante rutinene er

OnRButtonDown(): Identifikasjon er lagt til høyre museknapp. (Venstre museknapp roterer figuren.) 

void CStdView::OnRButtonDown(UINT nFlags, CPoint point)
{
  // User has clicked with right button to
  // identify an object
  GLint oldHilite=m_hilited;
  m_hilited=PickObject(point.x,point.y);
  if (m_hilited!=oldHilite)
    RedrawWindow();
  CView::OnRButtonDown(nFlags,point);
}

PickObject(): Dette er rutina som setter opp og tolker selve identifikasjonsmekanismen 

int CStdView::PickObject(int x, int y)
// params are screencoordinates
{
  // called when mousedown to identify an object, if any

  // make sure we activate the rendring context
  wglMakeCurrent(m_hDC,m_hRC);


  GLuint selectBuf[BUFSIZE]; // to store OGLs reports
  GLint hits;                // to count hit objects
  GLint viewport[4];
  glGetIntegerv(GL_VIEWPORT,viewport); // get existing viewport
  glSelectBuffer(BUFSIZE,selectBuf); // tell OGL where to report
  glRenderMode(GL_SELECT);  // as opposed to GL_RENDER
  glInitNames();  // init naming mechanism
  glPushName(99);// for later pops and pushes.
  glMatrixMode(GL_PROJECTION);
  glPushMatrix();
  glLoadIdentity();

  // set up a small clipping pyramid
  gluPickMatrix((GLdouble)x,(GLdouble)(viewport[3]-y),//center
                5.0f,5.0f,// extension
                viewport);

  // same view as in OnSize
  CRect R;
  GetClientRect(&R);
  gluPerspective( 60.0f,
           (GLdouble)R.Width()/(GLdouble)R.Height(),
           0.1f,70.0f);
  glMatrixMode(GL_MODELVIEW);

  DrawScene(GL_SELECT);  // draw without rendering

  glMatrixMode(GL_PROJECTION);
  glPopMatrix();
  hits=glRenderMode(GL_RENDER);  // gives me a hitcount

  // release the rendring context
  wglMakeCurrent(0,0);


  // process the hits
  // selectBuf contents for each hit:
  // ix  : number of names on the hitstack when hit occurred
  // ix+1: min z-depth of "object" associated with name
  // ix+2: max z-depth of "object" associated with name
  // ix+3: the name, ie index, assosiated with the hit
  if(hits ==0)
    return NO_OBJECT;
  else
  {
    // we have hit one or more "objects"
    // if only one we simply select it
    if(hits ==1)
      return selectBuf[3];//the only one in store

    // more than one is hit.  Which should we select ?
    // The closest one,
    // go for the one which closest part is closest
    GLint closestix=0;
    for(GLint ix=1;ix<hits;ix++)
      if(selectBuf[4*ix+1]<selectBuf[4*closestix+1])
        closestix=ix;
    return selectBuf[4*closestix+3];
  }
}

DrawScene(): Er modifisert for å ta vare på navngiving av figurelementer. Det er dessuten lagt inn en enkel effektivisering i det tilfelle at tegningen ikke skal rendres. 

void CStdView::DrawScene(GLenum mode/*=GL_RENDER*/)
{
  < whatever initialization and basic transformation >
  // draw a chain of toruser around origo
  int ix;
  int n=20;
  GLfloat bigR=15.0f;
  GLfloat ringR=4.0f;
  GLfloat thickR=0.5f;
  for (ix=0;ix< n; ix++)
  {
    glPushMatrix();
    if(ix%2==1)
    {
      glRotatef((360.0f*ix)/
          (1.0f*n)+(0.25f*360.0f/(1.0f*n))
           ,0.0f,0.0f,1.0f);
      glTranslatef(bigR,0.0f,0.0f);
      glRotatef(90.0,0.0f,1.0f,0.0f);
  }
  else
  {
    glRotatef((360.0f*ix)/(1.0f*n),0.0f,0.0f,1.0f);
    glTranslatef(bigR,0.0f,0.0f);
  }
  if(m_hilited==ix)
    CMaterial::SetMaterial(RED_PLASTIC);
  else
    CMaterial::SetMaterial(GOLD);
  if(m_Drawing_Mode==GL_SELECT)
  {
    glLoadName(ix);
    DrawTorus(ringR,thickR,20,10);// faster
  }
  else
    DrawTorus(ringR,thickR,70,20);
  glPopMatrix();
  }
  < end the drawing >
}
[1]
  • Program som viser valgbare smultringer(JOGL/Netbeans): https://svnit.hiof.no/svn/psource/JOGL/hitme
  • VC++ programmet hitme.zip(VC++/gml)
    hitme.zip(VC++/.Net)
  • C/GLUT programmet: hitbox.c
Referanser
  1. The OpenGL Programming Guide, 6 editionDave Schreiner, Mason Woo,Jackie Neider,Tom Davies2007Addison-Wesley Professional0321481003www.opengl.org/documentation/red_book/14-03-2010
Vedlikehold
Børre Stenseth, revidert mai 2010
Forklaring av>Identifikasjon
til toppen
WXT 6
Valid HTML5
Valid CSS!