+++ /dev/null
-/*
- * Progressive Mesh type Polygon Reduction Algorithm
- * by Stan Melax (c) 1998
- * Permission to use any of this code wherever you want is granted..
- * Although, please do acknowledge authorship if appropriate.
- *
- * See the header file progmesh.h for a description of this module
- */
-
-#include <stdio.h>
-#include <math.h>
-#include <stdlib.h>
-#include <assert.h>
-#include <windows.h>
-
-#include "vector.h"
-#include "list.h"
-#include "MeshReducer.h"
-
-class tridata {
- public:
- int v[3]; // indices to vertex list
- // texture and vertex normal info removed for this demo
-};
-
-void ProgressiveMesh(List<Vector> &vert, List<tridata> &tri,
- List<int> &map, List<int> &permutation );
-
-/*
- * For the polygon reduction algorithm we use data structures
- * that contain a little bit more information than the usual
- * indexed face set type of data structure.
- * From a vertex we wish to be able to quickly get the
- * neighboring faces and vertices.
- */
-class Triangle;
-class Vertex;
-
-class Triangle {
- public:
- Vertex * vertex[3]; // the 3 points that make this tri
- Vector normal; // unit vector othogonal to this face
- Triangle(Vertex *v0,Vertex *v1,Vertex *v2);
- ~Triangle();
- void ComputeNormal();
- void ReplaceVertex(Vertex *vold,Vertex *vnew);
- int HasVertex(Vertex *v);
-};
-class Vertex {
- public:
- Vector position; // location of point in euclidean space
- int id; // place of vertex in original list
- List<Vertex *> neighbor; // adjacent vertices
- List<Triangle *> face; // adjacent triangles
- float objdist; // cached cost of collapsing edge
- Vertex * collapse; // candidate vertex for collapse
- Vertex(Vector v,int _id);
- ~Vertex();
- void RemoveIfNonNeighbor(Vertex *n);
-};
-List<Vertex *> vertices;
-List<Triangle *> triangles;
-
-
-Triangle::Triangle(Vertex *v0,Vertex *v1,Vertex *v2){
- assert(v0!=v1 && v1!=v2 && v2!=v0);
- vertex[0]=v0;
- vertex[1]=v1;
- vertex[2]=v2;
- ComputeNormal();
- triangles.Add(this);
- for(int i=0;i<3;i++) {
- vertex[i]->face.Add(this);
- for(int j=0;j<3;j++) if(i!=j) {
- vertex[i]->neighbor.AddUnique(vertex[j]);
- }
- }
-}
-Triangle::~Triangle(){
- int i;
- triangles.Remove(this);
- for(i=0;i<3;i++) {
- if(vertex[i]) vertex[i]->face.Remove(this);
- }
- for(i=0;i<3;i++) {
- int i2 = (i+1)%3;
- if(!vertex[i] || !vertex[i2]) continue;
- vertex[i ]->RemoveIfNonNeighbor(vertex[i2]);
- vertex[i2]->RemoveIfNonNeighbor(vertex[i ]);
- }
-}
-int Triangle::HasVertex(Vertex *v) {
- return (v==vertex[0] ||v==vertex[1] || v==vertex[2]);
-}
-void Triangle::ComputeNormal(){
- Vector v0=vertex[0]->position;
- Vector v1=vertex[1]->position;
- Vector v2=vertex[2]->position;
- normal = (v1-v0)*(v2-v1);
- if(magnitude(normal)==0)return;
- normal = normalize(normal);
-}
-void Triangle::ReplaceVertex(Vertex *vold,Vertex *vnew) {
- assert(vold && vnew);
- assert(vold==vertex[0] || vold==vertex[1] || vold==vertex[2]);
- assert(vnew!=vertex[0] && vnew!=vertex[1] && vnew!=vertex[2]);
- if(vold==vertex[0]){
- vertex[0]=vnew;
- }
- else if(vold==vertex[1]){
- vertex[1]=vnew;
- }
- else {
- assert(vold==vertex[2]);
- vertex[2]=vnew;
- }
- int i;
- vold->face.Remove(this);
- assert(!vnew->face.Contains(this));
- vnew->face.Add(this);
- for(i=0;i<3;i++) {
- vold->RemoveIfNonNeighbor(vertex[i]);
- vertex[i]->RemoveIfNonNeighbor(vold);
- }
- for(i=0;i<3;i++) {
- assert(vertex[i]->face.Contains(this)==1);
- for(int j=0;j<3;j++) if(i!=j) {
- vertex[i]->neighbor.AddUnique(vertex[j]);
- }
- }
- ComputeNormal();
-}
-
-Vertex::Vertex(Vector v,int _id) {
- position =v;
- id=_id;
- vertices.Add(this);
-}
-
-Vertex::~Vertex(){
- assert(face.num==0);
- while(neighbor.num) {
- neighbor[0]->neighbor.Remove(this);
- neighbor.Remove(neighbor[0]);
- }
- vertices.Remove(this);
-}
-void Vertex::RemoveIfNonNeighbor(Vertex *n) {
- // removes n from neighbor list if n isn't a neighbor.
- if(!neighbor.Contains(n)) return;
- for(int i=0;i<face.num;i++) {
- if(face[i]->HasVertex(n)) return;
- }
- neighbor.Remove(n);
-}
-
-
-float ComputeEdgeCollapseCost(Vertex *u,Vertex *v) {
- // if we collapse edge uv by moving u to v then how
- // much different will the model change, i.e. how much "error".
- // Texture, vertex normal, and border vertex code was removed
- // to keep this demo as simple as possible.
- // The method of determining cost was designed in order
- // to exploit small and coplanar regions for
- // effective polygon reduction.
- // Is is possible to add some checks here to see if "folds"
- // would be generated. i.e. normal of a remaining face gets
- // flipped. I never seemed to run into this problem and
- // therefore never added code to detect this case.
- int i;
- float edgelength = magnitude(v->position - u->position);
- float curvature=0;
-
- // find the "sides" triangles that are on the edge uv
- List<Triangle *> sides;
- for(i=0;i<u->face.num;i++) {
- if(u->face[i]->HasVertex(v)){
- sides.Add(u->face[i]);
- }
- }
- // use the triangle facing most away from the sides
- // to determine our curvature term
- for(i=0;i<u->face.num;i++) {
- float mincurv=1; // curve for face i and closer side to it
- for(int j=0;j<sides.num;j++) {
- // use dot product of face normals. '^' defined in vector
- float dotprod = u->face[i]->normal ^ sides[j]->normal;
- mincurv = min(mincurv,(1-dotprod)/2.0f);
- }
- curvature = max(curvature,mincurv);
- }
- // the more coplanar the lower the curvature term
- return edgelength * curvature;
-}
-
-void ComputeEdgeCostAtVertex(Vertex *v) {
- // compute the edge collapse cost for all edges that start
- // from vertex v. Since we are only interested in reducing
- // the object by selecting the min cost edge at each step, we
- // only cache the cost of the least cost edge at this vertex
- // (in member variable collapse) as well as the value of the
- // cost (in member variable objdist).
- if(v->neighbor.num==0) {
- // v doesn't have neighbors so it costs nothing to collapse
- v->collapse=NULL;
- v->objdist=-0.01f;
- return;
- }
- v->objdist = 1000000;
- v->collapse=NULL;
- // search all neighboring edges for "least cost" edge
- for(int i=0;i<v->neighbor.num;i++) {
- float dist;
- dist = ComputeEdgeCollapseCost(v,v->neighbor[i]);
- if(dist<v->objdist) {
- v->collapse=v->neighbor[i]; // candidate for edge collapse
- v->objdist=dist; // cost of the collapse
- }
- }
-}
-void ComputeAllEdgeCollapseCosts() {
- // For all the edges, compute the difference it would make
- // to the model if it was collapsed. The least of these
- // per vertex is cached in each vertex object.
- for(int i=0;i<vertices.num;i++) {
- ComputeEdgeCostAtVertex(vertices[i]);
- }
-}
-
-void Collapse(Vertex *u,Vertex *v){
- // Collapse the edge uv by moving vertex u onto v
- // Actually remove tris on uv, then update tris that
- // have u to have v, and then remove u.
- if(!v) {
- // u is a vertex all by itself so just delete it
- delete u;
- return;
- }
- int i;
- List<Vertex *>tmp;
- // make tmp a list of all the neighbors of u
- for(i=0;i<u->neighbor.num;i++) {
- tmp.Add(u->neighbor[i]);
- }
- // delete triangles on edge uv:
- for(i=u->face.num-1;i>=0;i--) {
- if(u->face[i]->HasVertex(v)) {
- delete(u->face[i]);
- }
- }
- // update remaining triangles to have v instead of u
- for(i=u->face.num-1;i>=0;i--) {
- u->face[i]->ReplaceVertex(u,v);
- }
- delete u;
- // recompute the edge collapse costs for neighboring vertices
- for(i=0;i<tmp.num;i++) {
- ComputeEdgeCostAtVertex(tmp[i]);
- }
-}
-
-void AddVertex(List<Vector> &vert){
- for(int i=0;i<vert.num;i++) {
- Vertex *v = new Vertex(vert[i],i);
- }
-}
-void AddFaces(List<tridata> &tri){
- for(int i=0;i<tri.num;i++) {
- Triangle *t=new Triangle(
- vertices[tri[i].v[0]],
- vertices[tri[i].v[1]],
- vertices[tri[i].v[2]] );
- }
-}
-
-Vertex *MinimumCostEdge(){
- // Find the edge that when collapsed will affect model the least.
- // This funtion actually returns a Vertex, the second vertex
- // of the edge (collapse candidate) is stored in the vertex data.
- // Serious optimization opportunity here: this function currently
- // does a sequential search through an unsorted list :-(
- // Our algorithm could be O(n*lg(n)) instead of O(n*n)
- Vertex *mn=vertices[0];
- for(int i=0;i<vertices.num;i++) {
- if(vertices[i]->objdist < mn->objdist) {
- mn = vertices[i];
- }
- }
- return mn;
-}
-
-void ProgressiveMesh(List<Vector> &vert, List<tridata> &tri,
- List<int> &map, List<int> &permutation)
-{
- AddVertex(vert); // put input data into our data structures
- AddFaces(tri);
- ComputeAllEdgeCollapseCosts(); // cache all edge collapse costs
- permutation.SetSize(vertices.num); // allocate space
- map.SetSize(vertices.num); // allocate space
- // reduce the object down to nothing:
- while(vertices.num > 0) {
- // get the next vertex to collapse
- Vertex *mn = MinimumCostEdge();
- // keep track of this vertex, i.e. the collapse ordering
- permutation[mn->id]=vertices.num-1;
- // keep track of vertex to which we collapse to
- map[vertices.num-1] = (mn->collapse)?mn->collapse->id:-1;
- // Collapse this edge
- Collapse(mn,mn->collapse);
- }
- // reorder the map list based on the collapse ordering
- for(int i=0;i<map.num;i++) {
- map[i] = (map[i]==-1)?0:permutation[map[i]];
- }
- // The caller of this function should reorder their vertices
- // according to the returned "permutation".
-}
-
+++ /dev/null
-
-#include <stdio.h>
-#include <math.h>
-#include <assert.h>
-
-#include "vector.h"
-
-float sqr(float a) {return a*a;}
-
-// vector (floating point) implementation
-
-float magnitude(Vector v) {
- return (float)sqrt(sqr(v.x) + sqr( v.y)+ sqr(v.z));
-}
-Vector normalize(Vector v) {
- float d=magnitude(v);
- if (d==0) {
- printf("Cant normalize ZERO vector\n");
- assert(0);
- d=0.1f;
- }
- v.x/=d;
- v.y/=d;
- v.z/=d;
- return v;
-}
-
-Vector operator+(Vector v1,Vector v2) {return Vector(v1.x+v2.x,v1.y+v2.y,v1.z+v2.z);}
-Vector operator-(Vector v1,Vector v2) {return Vector(v1.x-v2.x,v1.y-v2.y,v1.z-v2.z);}
-Vector operator-(Vector v) {return Vector(-v.x,-v.y,-v.z);}
-Vector operator*(Vector v1,float s) {return Vector(v1.x*s,v1.y*s,v1.z*s);}
-Vector operator*(float s, Vector v1) {return Vector(v1.x*s,v1.y*s,v1.z*s);}
-Vector operator/(Vector v1,float s) {return v1*(1.0f/s);}
-float operator^(Vector v1,Vector v2) {return v1.x*v2.x + v1.y*v2.y + v1.z*v2.z;}
-Vector operator*(Vector v1,Vector v2) {
- return Vector(
- v1.y * v2.z - v1.z*v2.y,
- v1.z * v2.x - v1.x*v2.z,
- v1.x * v2.y - v1.y*v2.x);
-}
-Vector planelineintersection(Vector n,float d,Vector p1,Vector p2){
- // returns the point where the line p1-p2 intersects the plane n&d
- Vector dif = p2-p1;
- float dn= n^dif;
- float t = -(d+(n^p1) )/dn;
- return p1 + (dif*t);
-}
-int concurrent(Vector a,Vector b) {
- return(a.x==b.x && a.y==b.y && a.z==b.z);
-}
-
-
-// Matrix Implementation
-matrix transpose(matrix m) {
- return matrix( Vector(m.x.x,m.y.x,m.z.x),
- Vector(m.x.y,m.y.y,m.z.y),
- Vector(m.x.z,m.y.z,m.z.z));
-}
-Vector operator*(matrix m,Vector v){
- m=transpose(m); // since column ordered
- return Vector(m.x^v,m.y^v,m.z^v);
-}
-matrix operator*(matrix m1,matrix m2){
- m1=transpose(m1);
- return matrix(m1*m2.x,m1*m2.y,m1*m2.z);
-}
-
-//Quaternion Implementation
-Quaternion operator*(Quaternion a,Quaternion b) {
- Quaternion c;
- c.r = a.r*b.r - a.x*b.x - a.y*b.y - a.z*b.z;
- c.x = a.r*b.x + a.x*b.r + a.y*b.z - a.z*b.y;
- c.y = a.r*b.y - a.x*b.z + a.y*b.r + a.z*b.x;
- c.z = a.r*b.z + a.x*b.y - a.y*b.x + a.z*b.r;
- return c;
-}
-Quaternion operator-(Quaternion q) {
- return Quaternion(q.r*-1,q.x,q.y,q.z);
-}
-Quaternion operator*(Quaternion a,float b) {
- return Quaternion(a.r*b, a.x*b, a.y*b, a.z*b);
-}
-Vector operator*(Quaternion q,Vector v) {
- return q.getmatrix() * v;
-}
-Vector operator*(Vector v,Quaternion q){
- assert(0); // must multiply with the quat on the left
- return Vector(0.0f,0.0f,0.0f);
-}
-
-Quaternion operator+(Quaternion a,Quaternion b) {
- return Quaternion(a.r+b.r, a.x+b.x, a.y+b.y, a.z+b.z);
-}
-float operator^(Quaternion a,Quaternion b) {
- return (a.r*b.r + a.x*b.x + a.y*b.y + a.z*b.z);
-}
-Quaternion slerp(Quaternion a,Quaternion b,float interp){
- if((a^b) <0.0) {
- a.r=-a.r;
- a.x=-a.x;
- a.y=-a.y;
- a.z=-a.z;
- }
- float theta = (float)acos(a^b);
- if(theta==0.0f) { return(a);}
- return a*(float)(sin(theta-interp*theta)/sin(theta)) + b*(float)(sin(interp*theta)/sin(theta));
-}
-
+++ /dev/null
-//
-// This module contains a bunch of well understood functions
-// I apologise if the conventions used here are slightly
-// different than what you are used to.
-//
-
-#ifndef GENERIC_VECTOR_H
-#define GENERIC_VECTOR_H
-
-#include <stdio.h>
-#include <math.h>
-
-
-class Vector {
- public:
- float x,y,z;
- Vector(float _x=0.0,float _y=0.0,float _z=0.0){x=_x;y=_y;z=_z;};
- operator float *() { return &x;};
-};
-
-float magnitude(Vector v);
-Vector normalize(Vector v);
-
-Vector operator+(Vector v1,Vector v2);
-Vector operator-(Vector v);
-Vector operator-(Vector v1,Vector v2);
-Vector operator*(Vector v1,float s) ;
-Vector operator*(float s,Vector v1) ;
-Vector operator/(Vector v1,float s) ;
-float operator^(Vector v1,Vector v2); // DOT product
-Vector operator*(Vector v1,Vector v2); // CROSS product
-Vector planelineintersection(Vector n,float d,Vector p1,Vector p2);
-
-class matrix{
- public:
- Vector x,y,z;
- matrix(){x=Vector(1.0f,0.0f,0.0f);
- y=Vector(0.0f,1.0f,0.0f);
- z=Vector(0.0f,0.0f,1.0f);};
- matrix(Vector _x,Vector _y,Vector _z){x=_x;y=_y;z=_z;};
-};
-matrix transpose(matrix m);
-Vector operator*(matrix m,Vector v);
-matrix operator*(matrix m1,matrix m2);
-
-class Quaternion{
- public:
- float r,x,y,z;
- Quaternion(){x=y=z=0.0f;r=1.0f;};
- Quaternion(Vector v,float t){v=normalize(v);r=(float)cos(t/2.0);v=v*(float)sin(t/2.0);x=v.x;y=v.y;z=v.z;};
- Quaternion(float _r,float _x,float _y,float _z){r=_r;x=_x;y=_y;z=_z;};
- float angle(){return (float)(acos(r)*2.0);}
- Vector axis(){Vector a(x,y,z); return a*(float)(1/sin(angle()/2.0));}
- Vector xdir(){return Vector(1-2*(y*y+z*z), 2*(x*y+r*z), 2*(x*z-r*y));}
- Vector ydir(){return Vector( 2*(x*y-r*z),1-2*(x*x+z*z), 2*(y*z+r*x));}
- Vector zdir(){return Vector( 2*(x*z+r*y), 2*(y*z-r*x),1-2*(x*x+y*y));}
- matrix getmatrix(){return matrix(xdir(),ydir(),zdir());}
- //operator matrix(){return getmatrix();}
-};
-Quaternion operator-(Quaternion q);
-Quaternion operator*(Quaternion a,Quaternion b);
-Vector operator*(Quaternion q,Vector v);
-Vector operator*(Vector v,Quaternion q);
-Quaternion slerp(Quaternion a,Quaternion b,float interp);
-
-#endif
OSDN Git Service
