Transcript CS 497: Computer Graphics

CS 497: Computer
Graphics
James Money
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
Implementing
Perspective Projections
The basis of almost all current 3D
graphics engines are polygonal based
systems. Therefore, today we will
concentrate on developing the
polygonal engine basics for your next
project with one major exception:
Clipping in 4D. We will discuss that
tomorrow.
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
What is a polygon?
• A polygon is a closed series of points
connected by straight lines.
• In our case, the polygon is planar.
– That means all points exist on a plane.
• A polygon is filled by flooding the
interior of the connecting points.
Not Filled
Polygons
Filled
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
How does we represent
a polygon?
• Way 1: Set of Points
• Way 2: Pointers to the vertexes that
make up the points.
• Way 3: A list of edges that point to
vertices.
We will use Way 2 for our engine. It will
come clear soon, why we use that
method.
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
Vertex Pointer
Representation
• Polygon 1
• Vertex A
– Vertex 1
– Vertex 2
– Vertex 3
• Polygon 2
–
–
–
–
Vertex 1
Vertex 2
Vertex 3
Vertex 4
– X,Y,Z values
– List of polygons
sharing this vertex
•
•
•
•
Vertex B
Vertex C
Vertex D
Vertex E
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
Vertex Object
This object has:
– A Point3D object
– A pointer to a list of polygons(Polygon3D**)
– The number of polygons in that list that are
valid.
– The max number of polygons that can be
in the list.
– A pointer to the next vertex, or NULL.
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
Vertex Object
Class Vertex{
public:
Vertex(int num=10);
Vertex(double xVal, double yVal, double zVal);
Vertex(Vertex &v);
~Vertex();
Polygon3D * GetNthPolygon(int index);
void SetNthPolygon(int index, Polygon3D * poly);
void AddPolygon(Polygon3D *poly);
void DeletePolygon(Polygon3D *poly);
int GetNumPolygons(void) { return numItems; };
Vertex *next;
private:
Point3D pt;
Polygon3D **list;
int maxNum,numItems;
};
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
Vertex Object
Vertex::Vertex(int num=10){
pt.x=pt.y=pt.z=0;
maxNum=num;
numItems=0;
list=new Polygon3D * [maxNum];
if (!list) return;
for(int i=0;i<maxNum;i++) list[i]=NULL;
next=NULL;
}
Vertex::~Vertex(){
if (list) delete[] list;
list=NULL;
maxNum=numItems=0;
next=NULL;
} Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
Vertex Object
void Vertex::AddPolygon(Polygon3D *poly){
if (!list) return;
for(int i=0;i<numItem;i++)
if (list[i]==poly) return;
if (numItems>=maxNum){
Polygon3D **temp;
maxNum*=2;
temp=new Polygon3D * [maxNum];
if (!temp) return;
for(int j=0;j<numItems;j++) temp[j]=list[j];
for(int k=numItems;k<maxNum;k++) temp[k]=NULL;
delete[] list;
list=temp;
}
numItems++;
list[numItems-1]=poly;
}
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
Vertex Object
void Vertex::DeletePolygon(Polygon3D *poly){
if (!list) return;
for(int i=0;i<numItem;i++)
if (list[i]==poly){
for(int j=i+1;j<numItems;j++)list[j-1]=list[j];
numItems--;
return;
}
}
Polygon3D * Vertex::GetNthPolygon(int index){
if (index>=numItem) return NULL;
if (!list) return NULL;
return list[index];
}
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
Vertex Object
void Vertex::SetNthPolygon(int index, Polygon3D * poly){
if (index>=numItem) return;
if (!list) return;
list[index]=poly;
}
Vertex::Vertex(double xVal, double yVal, double zVal){
pt.x=xVal;
pt.y=yVal;
pt.z=zVal;
maxNum=10;
numItems=0;
list=new Polygon3D * [maxNum];
if (!list) return;
for(int i=0;i<maxNum;i++) list[i]=NULL;
next=null;
}
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
Vertex Object
Vertex::Vertex(Vertex &v){
maxNum=v.maxNum;
numItem=v.numItems;
pt.x=v.pt.x;
pt.y=v.pt.y;
pt.z=v.pt.z;
list=new Polygon3D * [maxNum];
if (!list) return;
for(int i=0;i<numItems;i++) list[i]=v.list[i];
next=v.next;
}
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
VertexList Object
This object has:
– The number of vertices in the list.
– The max number of vertices in list.
– A pointer to a list of Vertices(Vertex **).
– A hashing function that locates a vertex
quickly in the list.
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
Hashing? What’s that?
Flattened Hash Browns?
The list we made is a hash table.
We use the hash function to return us a
index number into the table given the
Vertex.
If the index it gives us is not correct, we
follow the next vertex pointer until we
find the correct vertex.
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
Hash Tables
Null
Hash
Vertex 1 Null
Null
Table
Vertex 2
Vertex 3 Null
Entries
Null
Null
Our hash function does this for a table of 1000 entries:
int VertexList::Hash(Vertex &v){
return (v.x%1000 + v.y%100 + v.z%10);
}
In General:
v.x%tblSz + v.y%(tblSz/10) + v.z%(tblSz/100);
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
VertexList Object
class VertexList{
public:
VertexList(int size);
~VertexList();
Vertex * FindVertex(double x,y,z);
Vertex * AddVertex(double x,y,z);
void DeleteVertex(double x,y,z);
private:
int tblSize,maxNum;
Vertex **list;
};
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
VertexList Object
Our object is created by:
VertexList::VertexList(int size){
tblSz=size;
maxNum=(tblSz - 1) + (tblSz/10 - 1) +
(tblSz/100 - 1);
list=new Vertex * [maxNum];
if (!list) return;
for(int i=0;i<maxNum;i++) list[i]=NULL;
}
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
VertexList Object
VertexList::~VertexList(){
if (list){
for(int i=0;i<numItems;i++)
if (list[i]){
Vertex *item=list[i];
while (item){
Vertex *next=item->next;
delete item;
item=next;
}
}
delete[] list;
}
list=NULL;
tblSz=0;
maxNum=0;
}
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
VertexList Object
Our object has a search function:
Vertex * FindVertex(double x,y,z){
int index=hash(x,y,z);
Vertex *item;
if (!list) return NULL;
item=list[index];
while (item){
if ((item->pt.x==x) && (item->pt.y==y)
&&(item->pt.z==z)) return item;
item=item->next;
}
return NULL;
}
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
Vertex * AddVertex(double x,y,z){
int index=hash(x,y,z);
Vertex *item,*prev;
if (!list) return NULL;
item=list[index];
prev=NULL;
while (item){
if ((item->pt.x==x) && (item->pt.y==y)
&&(item->pt.z==z)) return item;
prev=item;
item=item->next;
}
Vertex *newItem=new Vertex(x,y,z);
if (prev==NULL)
vertexlist[index]=newItem;
else prev->next=newItem;
return newItem;
}
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
void DeleteVertex(double x,y,z){
int index=hash(x,y,z);
Vertex *item,*prev;
if (!list) return;
item=list[index];
prev=NULL;
while (item){
if ((item->pt.x==x) && (item->pt.y==y)
&&(item->pt.z==z)) break;
prev=item;
item=item->next;
}
if (!item) return;
if (!prev)
vertexlist[index]=item->next;
else prev->next=item->next;
delete item;
}
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
VertexList Object
Now we can add a vertex to the list, and it
will not be duplicated. All we have to do
with the returned Vertex is add our
polygon to the polygon list.
We’ve saved a lot of space with the
method as well: no duplicated points!
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
Polygon3D Object
So now what is a polygon?
– A list of vertex pointers that point to entries
in the VertexList Hash Table.
– Functions for creation and destruction.
– Functions to transform, normalize, clip, and
map out points to our drawing window.
– Functions to add points to the list of
vertices.
– Functions to fill and draw the polygon.
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
class Polygon3D{
Polygon3D(VertexList *list,int num=5);
Polygon3D(Polygon3D &poly);
~Polygon3D();
AddPoint(double x,y,z);
Fill(HDC hDC,COLORREF color);
Draw(HDC hDC,COLORREF color);
Fill(HDC hDC, COLORREF (*ColorFunc )(double x,y,z));
private:
void Transform(Graphics3D &g);
void Normalize(Graphics3D &g);
void Clip(Graphics3D &g);
void Map(Graphics3D &g);
Vertex **pts;
VertexList *hashTable;
int numPoints,maxNum,numClippedPoints,maxClippedPoints;
Vector *TransformedPts,*NormalizedPts,*ClippedPts;
Point3D *pts2D;
Vector *Normal,*TransformedNormal;
};
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.
Polygon3D Object
For the destructor we must:
– Delete the references to that polygon in
each vertex.
• If there are no more polygons in the vertex,
delete the vertex from the hash table and the
vertex itself.
– Delete all the other data structures
normally.
Copyright  1999 by James H. Money. All rights reserved. Except as permitted under United States Copyright Act of 1976, no part of this publication may be
reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written permission of the author.