20 #define min(x,y) (((x) <= (y)) ? (x) : (y))
21 #define max(x,y) (((x) >= (y)) ? (x) : (y))
38 Triangle(Vertex *v0,Vertex *
v1,Vertex *
v2);
41 void ReplaceVertex(Vertex *vold,Vertex *vnew);
42 int HasVertex(Vertex *v);
48 List<Vertex *> neighbor;
49 List<Triangle *> face;
52 Vertex(Vector v,
int _id);
54 void RemoveIfNonNeighbor(Vertex *n);
56 List<Vertex *> vertices;
57 List<Triangle *> triangles;
60 Triangle::Triangle(Vertex *v0,Vertex *
v1,Vertex *
v2){
61 assert(v0!=v1 && v1!=v2 && v2!=v0);
67 for(
int i=0;i<3;i++) {
68 vertex[i]->face.Add(
this);
69 for(
int j=0;j<3;j++)
if(i!=j) {
70 vertex[i]->neighbor.AddUnique(vertex[j]);
74 Triangle::~Triangle(){
76 triangles.Remove(
this);
78 if(vertex[i]) vertex[i]->face.Remove(
this);
82 if(!vertex[i] || !vertex[i2])
continue;
83 vertex[i ]->RemoveIfNonNeighbor(vertex[i2]);
84 vertex[i2]->RemoveIfNonNeighbor(vertex[i ]);
87 int Triangle::HasVertex(Vertex *v) {
88 return (v==vertex[0] ||v==vertex[1] || v==vertex[2]);
90 void Triangle::ComputeNormal(){
91 Vector v0=vertex[0]->position;
92 Vector v1=vertex[1]->position;
93 Vector v2=vertex[2]->position;
94 normal = (v1-v0)*(v2-v1);
95 if(magnitude(normal)==0)
return;
98 void Triangle::ReplaceVertex(Vertex *vold,Vertex *vnew) {
100 assert(vold==vertex[0] || vold==vertex[1] || vold==vertex[2]);
101 assert(vnew!=vertex[0] && vnew!=vertex[1] && vnew!=vertex[2]);
105 else if(vold==vertex[1]){
109 assert(vold==vertex[2]);
113 vold->face.Remove(
this);
114 assert(!vnew->face.Contains(
this));
115 vnew->face.Add(
this);
117 vold->RemoveIfNonNeighbor(vertex[i]);
118 vertex[i]->RemoveIfNonNeighbor(vold);
121 assert(vertex[i]->face.Contains(
this)==1);
122 for(
int j=0;j<3;j++)
if(i!=j) {
123 vertex[i]->neighbor.AddUnique(vertex[j]);
129 Vertex::Vertex(Vector v,
int _id) {
137 while(neighbor.num) {
138 neighbor[0]->neighbor.Remove(
this);
139 neighbor.Remove(neighbor[0]);
141 vertices.Remove(
this);
143 void Vertex::RemoveIfNonNeighbor(Vertex *n) {
145 if(!neighbor.Contains(n))
return;
146 for(
int i=0;i<face.num;i++) {
147 if(face[i]->HasVertex(n))
return;
153 float ComputeEdgeCollapseCost(Vertex *u,Vertex *v) {
166 float edgelength = magnitude(v->position - u->position);
170 List<Triangle *> sides;
171 for(i=0;i<u->face.num;i++) {
172 if(u->face[i]->HasVertex(v)){
173 sides.Add(u->face[i]);
178 for(i=0;i<u->face.num;i++) {
180 for(
int j=0;j<sides.num;j++) {
182 float dotprod = u->face[i]->normal ^ sides[j]->normal;
183 mincurv =
min(mincurv,(1-dotprod)/2.0
f);
185 curvature =
max(curvature,mincurv);
188 return edgelength * curvature;
191 void ComputeEdgeCostAtVertex(Vertex *v) {
198 if(v->neighbor.num==0) {
204 v->objdist = 1000000;
207 for(
int i=0;i<v->neighbor.num;i++) {
209 dist = ComputeEdgeCollapseCost(v,v->neighbor[i]);
210 if(dist<v->objdist) {
211 v->collapse=v->neighbor[i];
216 void ComputeAllEdgeCollapseCosts() {
220 for(
int i=0;i<vertices.num;i++) {
221 ComputeEdgeCostAtVertex(vertices[i]);
225 void Collapse(Vertex *u,Vertex *v){
237 for(i=0;i<u->neighbor.num;i++) {
238 tmp.Add(u->neighbor[i]);
241 for(i=u->face.num-1;i>=0;i--) {
242 if(u->face[i]->HasVertex(v)) {
247 for(i=u->face.num-1;i>=0;i--) {
248 u->face[i]->ReplaceVertex(u,v);
252 for(i=0;i<tmp.num;i++) {
253 ComputeEdgeCostAtVertex(tmp[i]);
257 void AddVertex(List<Vector> &vert){
258 for(
int i=0;i<vert.num;i++) {
259 new Vertex(vert[i],i);
262 void AddFaces(List<tridata> &tri){
263 for(
int i=0;i<tri.num;i++) {
265 vertices[tri[i].v[0]],
266 vertices[tri[i].v[1]],
267 vertices[tri[i].v[2]] );
271 Vertex *MinimumCostEdge(){
278 Vertex *mn=vertices[0];
279 for(
int i=0;i<vertices.num;i++) {
280 if(vertices[i]->objdist < mn->objdist) {
287 void ProgressiveMesh(List<Vector> &vert, List<tridata> &tri,
288 List<int> &map, List<int> &permutation)
292 ComputeAllEdgeCollapseCosts();
293 permutation.SetSize(vertices.num);
294 map.SetSize(vertices.num);
296 while(vertices.num > 0) {
298 Vertex *mn = MinimumCostEdge();
300 permutation[mn->id]=vertices.num-1;
302 map[vertices.num-1] = (mn->collapse)?mn->collapse->id:-1;
304 Collapse(mn,mn->collapse);
307 for(
int i=0;i<map.num;i++) {
308 map[i] = (map[i]==-1)?0:permutation[map[i]];