КР580[2]

19 октября 2004 г. от кого-то с адреса bear_fami***@m*****.ru, не без
помощи сервера mx1.mail.ru (IP 195.162.43.58)мне в ящик свалилось
какое-то непонятное письмо по теме "КР580[2]", на что через
осмысливания я решил высказаться:

Так-так-так... Можно скооперироваться. Планирую написать эмулятор
микролаба, возможно расширяемый. Это как курсовик. А вообще я и old
school фанат и студент... :)

Hello аll,

Помогите, пожалуйста разобраться с BSP-компилятором.
Суть в следующем: следующая программа boolean.cpp должна производить
операцию вычитания одного многогранника (куба) из другого (цилиндра)
с помощью BSP-деревьев. Использует GLUT:

/*boolean.cpp*/

#include <GL/gl.h>
#include <GL/glu.h>
#include <GL/glut.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <algorithm>

/* Simple Vector3d class */

class Vector3d {
public:
Vector3d() {}
Vector3d(float nx, float ny, float nz) {
x = nx;
y = ny;
z = nz;
}

friend Vector3d operator+(const Vector3d &a, const Vector3d &b) {
return Vector3d(a.x+b.x, a.y+b.y, a.z+b.z);
}

friend Vector3d operator-(const Vector3d &a, const Vector3d &b) {
return Vector3d(a.x-b.x, a.y-b.y, a.z-b.z);
}

friend Vector3d operator*(const Vector3d &a, float s) {
return Vector3d(a.x*s, a.y*s, a.z*s);
}

friend Vector3d operator/(const Vector3d &a, float s) {
return a*(1.0f/s);
}

friend float operator*(const Vector3d &a, const Vector3d &b) {
return a.x*b.x + a.y*b.y + a.z*b.z;
}

void operator*=(float s) {
x *= s;
y *= s;
z *= s;
}

void operator/=(float s) {
*this *= (1.0f/s);
}

void operator+=(const Vector3d &b) { x+=b.x; y+=b.y; z+=b.z; }

void operator-=(const Vector3d &b) { x-=b.x; y-=b.y; z-=b.z; }

void operator=(const Vector3d &b) {
x = b.x; y = b.y; z = b.z;
}

float length() {
return sqrtf(x*x + y*y + z*z);
}

Vector3d normalize() {
return *this / length();
}

Vector3d cross(const Vector3d &b) {
return Vector3d(y*b.z - b.y*z,
z*b.x - b.z*x,
x*b.y - b.x*y);
}

Vector3d transform() {
float m[16];
glGetFloatv(GL_MODELVIEW_MATRIX, m);
return Vector3d(m[0]*x + m[4]*y + m[8]*z + m[12],
m[1]*x + m[5]*y + m[9]*z + m[13],
m[2]*x + m[6]*y + m[10]*z + m[14]);
}

float x, y, z;
};

/* BSP Node including a polygon */

class BSPNode;

BSPNode *move_bspnodes(BSPNode *to, BSPNode *add);

enum Side {
InnerSide,
OuterSide
};

class BSPNode {
public:
BSPNode() {
left = 0;
right = 0;
}

~BSPNode() {
if(left) delete left;
if(right) delete right;
}

BSPNode *copy() {
BSPNode *n = new BSPNode();
*n = *this;
if(left) n->left = left->copy();
if(right) n->right = right->copy();
return n;
}

void insertBSPNode(BSPNode *n) {
/* First insert subnodes */
if(n->left) insertBSPNode(n->left);
if(n->right) insertBSPNode(n->right);

/* Split polygon */
BSPNode *l, *r;
splitPolygon(n, &l, &r);

/* Insert pieces to left and right */
if(l) {
if(left) {
left->insertBSPNode(l);
delete l;
} else left = l;
}
if(r) {
if(right) {
right->insertBSPNode(r);
delete r;
}
else right = r;
}
}

BSPNode *getSide(Side side, BSPNode *n) {
/* Recurse subnodes */
BSPNode *polys = 0;
if(n->left) polys = getSide(side, n->left);
if(n->right) polys = move_bspnodes(polys, getSide(side, n->right));

/* Split... */
BSPNode *l, *r;
splitPolygon(n, &l, &r);

if(l) {
if(left) {
polys = move_bspnodes(polys, left->getSide(side, l));
delete l;
} else {
if(side == InnerSide) {
polys = move_bspnodes(polys, l);
}
else delete l;
}
}
if(r) {
if(right) {
polys = move_bspnodes(polys, right->getSide(side, r));
delete r;
}
else {
if(side == OuterSide) {
polys = move_bspnodes(polys, r);
}
else delete r;
}
}
return polys;
}

void splitPolygon(BSPNode *p, BSPNode **l, BSPNode **r) {
unsigned int i;

*l = new BSPNode();
*r = new BSPNode();

/* Check side */
float *dists = new float [p->polygon.size()];
float min = 0, max = 0;
for(i=0; i<p->polygon.size(); i++) {
dists[i] = getPointDistance(p->polygon[i]);
if(dists[i] < min) min = dists[i];
if(dists[i] > max) max = dists[i];
}

/* If everything is on the left side... */
if(max < 0.001) {
for(i=0; i<p->polygon.size(); i++) {
(*l)->addVertex(p->polygon[i]);
}
}
/* Or on the right side... */
else if(min > -0.001) {
for(i=0; i<p->polygon.size(); i++) {
(*r)->addVertex(p->polygon[i]);
}
}
/* On both sides, have to split some... */
else {
for(i=0; i<p->polygon.size(); i++) {
Vector3d &p1 = p->polygon[i];
Vector3d &p2 = p->polygon[(i+1)%p->polygon.size()];
float d1 = dists[i];
float d2 = dists[(i+1)%p->polygon.size()];

if(d1 < 0) {
(*l)->addVertex(p1);
if(d2 > 0) {
Vector3d v = p1 + (p2 - p1) * -d1 / (d2-d1);
(*l)->addVertex(v);
(*r)->addVertex(v);
}
}
else {
(*r)->addVertex(p1);
if(d2 < 0) {
Vector3d v = p1 + (p2 - p1) * -d1 / (d2-d1);
(*l)->addVertex(v);
(*r)->addVertex(v);
}
}
}
}

delete [] dists;

if((*l)->polygon.size() <= 2) {
delete *l;
*l = 0;
} else {
(*l)->normal = p->normal;
(*l)->dist = p->dist;
}
if((*r)->polygon.size() <= 2) {
delete *r;
*r = 0;
} else {
(*r)->normal = p->normal;
(*r)->dist = p->dist;
}
}

float getPointDistance(const Vector3d &p) {
return normal * p - dist;
}

void reverseNormal() {
if(left) left->reverseNormal();
if(right) right->reverseNormal();
normal *= -1;
reverse(polygon.begin(), polygon.end());
}

void calculatePlane() {
normal = (polygon[1]-polygon[0]).cross(polygon[2]-polygon[0]);
normal = normal.normalize();
dist = normal * polygon[0];
}

void addVertex(const Vector3d &v) {
polygon.push_back(v);
}

void render(const Vector3d &colour) {
if(left) left->render(colour);
if(right) right->render(colour);

// glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
glBegin(GL_POLYGON);
glColor3fv(&colour.x);
glNormal3fv(&normal.x);
for(unsigned int i=0; i<polygon.size(); i++) {
glVertex3fv(&polygon[i].x);
}
glEnd();
}

Vector3d normal;
float dist;
std::vector<Vector3d> polygon;
BSPNode *left, *right;
};

BSPNode *move_bspnodes(BSPNode *to, BSPNode *add) {
if(add) {
if(to) {
to->insertBSPNode(add);
delete add;
}
else return add;
}
return to;
}

BSPNode *new_quad(const Vector3d &v1, const Vector3d &v2,
const Vector3d &v3, const Vector3d &v4) {
BSPNode *n = new BSPNode();

return n;
}

Vector3d get_cylinder_vertex(float r, float h, float a, float y) {
Vector3d v = Vector3d(cos(3.1415*2*a)*r, sin(3.1415*2*a)*r, h/2-y*h);
return v.transform();
}

BSPNode *create_cylinder(float r, float h, int slices) {
int i;
BSPNode *root = new BSPNode();
for(i=0; i<slices; i++) {
root->addVertex(get_cylinder_vertex(r, h, i/(float)slices, 0));
}
root->calculatePlane();

BSPNode *top = new BSPNode();
for(i=slices-1; i>=0; i--) {
top->addVertex(get_cylinder_vertex(r, h, i/(float)slices, 1));
}
top->calculatePlane();
root->insertBSPNode(top);

for(i=0; i<slices; i++) {
BSPNode *n = new BSPNode();
n->addVertex(get_cylinder_vertex(r, h, i/(float)slices, 0));
n->addVertex(get_cylinder_vertex(r, h, i/(float)slices, 1));
n->addVertex(get_cylinder_vertex(r, h, (i+1)/(float)slices, 1));
n->addVertex(get_cylinder_vertex(r, h, (i+1)/(float)slices, 0));
n->calculatePlane();
root->insertBSPNode(n);
}

return root;
}

BSPNode *create_box(float x, float y, float z) {
Vector3d verts[] = { Vector3d(-x, -y, -z), Vector3d(x, -y, -z),
Vector3d(-x, y, -z), Vector3d(x, y, -z),
Vector3d(-x, -y, z), Vector3d(x, -y, z),
Vector3d(-x, y, z), Vector3d(x, y, z) };
for(int i=0; i<8; i++) {
verts[i] = verts[i].transform();
}

BSPNode *root = new_quad(verts[0], verts[2], verts[3], verts[1]);
root->insertBSPNode(new_quad(verts[4], verts[5], verts[7], verts[6]));
root->insertBSPNode(new_quad(verts[6], verts[7], verts[3], verts[2]));
root->insertBSPNode(new_quad(verts[0], verts[1], verts[5], verts[4]));
root->insertBSPNode(new_quad(verts[5], verts[1], verts[3], verts[7]));
root->insertBSPNode(new_quad(verts[0], verts[4], verts[6], verts[2]));
return root;
}

BSPNode *obj, *obj2;

void init() {
GLfloat light_position[] = { 1.0, 1.0, -1.0, 0.0 };
GLfloat light_colour[] = { 1.0, 1.0, 1.0, 1.0 };

glLightfv(GL_LIGHT0, GL_POSITION, light_position);
glLightfv(GL_LIGHT0, GL_DIFFUSE, light_colour);
glEnable(GL_LIGHT0);
glEnable(GL_LIGHTING);
glEnable(GL_COLOR_MATERIAL);
glEnable(GL_DEPTH_TEST);
glShadeModel(GL_SMOOTH);
glEnable(GL_CULL_FACE);
glCullFace(GL_BACK);

glClearColor(1.0, 1.0, 1.0, 0.0);

glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
obj = create_cylinder(1.0, 4, 16);
}

static float currenttime = 0;

void display() {
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

glMatrixMode(GL_MODELVIEW);
glLoadIdentity();

glPushMatrix();
glTranslatef(sin(currenttime*0.5)*1.5, 0.0, cos(currenttime*0.6)*2);
glRotatef(currenttime*100.0f, 0, 1, 0);
glRotatef(currenttime*110.0f, 0, 0, 1);
obj2 = create_box(1.0, 1.0, 1.0);
glPopMatrix();

BSPNode *o;

o = obj->getSide(InnerSide, obj2);
if(o) {
o->reverseNormal();
o->render(Vector3d(0.4, 0.4, 1.0));
delete o;
}
o = obj2->getSide(OuterSide, obj);
if(o) {
o->render(Vector3d(1.0, 0.4, 0.4));
delete o;
}

delete obj2;

glFlush();
glutSwapBuffers();
}

void timer(int value) {
currenttime += 0.005;
glutPostRedisplay();
glutTimerFunc(10, timer, 0);
}

void reshape(int w, int h) {
glViewport(0, 0, w, h);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluPerspective(40.0, (float)w / (float)h, 0.1, 10.0);
gluLookAt(4,3,-5, 0,0,0, 0,1,0);
}

int main(int argc, char *argv[]) {
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB | GLUT_DEPTH);
glutInitWindowSize(400, 400);
glutCreateWindow("Boolean operations");
init();
glutDisplayFunc(display);
glutReshapeFunc(reshape);
glutTimerFunc(10, timer, 0);
glutMainLoop();
return 0;
}

У меня стоит glut 3.7 beta.
Компилирую с помощью Microsoft Visual C++ 6.0.
Я создаю консольное приложение (File->New->Win32 Console Application; Platform:
Win32),
делаю "An empty project", а затем добавляю в "Source Files" файл boolean.cpp.

В опциях компоновщика (Project -> Settings -> Link -> Object/library modules)
впереди всего
дописываю: glut32.lib glu32.lib opengl32.lib.

При нажатии F7 (Build Project) выдаются следующие ошибки:

...
c:\program files\microsoft visual studio\vc98\include\gl\gl.h(1152) : error C2144:
syntax error : missing ';' before type 'void'
c:\program files\microsoft visual studio\vc98\include\gl\gl.h(1152) : error C2501:
'WINGDIAPI' : missing storage-class or type specifiers
c:\program files\microsoft visual studio\vc98\include\gl\gl.h(1152) : fatal error
C1004: unexpected end of file found
Error executing cl.exe.

_boolean.exe - 3 error(s), 0 warning(s)

Если же в начале файла переставить директивы включения header-ов следующим образом:
#include <GL/glut.h>
#include <GL/gl.h>
#include <GL/glu.h>
...
(то есть если glut.h включить первым),
то выдается следующая ошибка (одна):

...
d:\projects\_boolean\boolean.cpp(256) : error C2065: 'reverse' : undeclared identifier
Error executing cl.exe.

_boolean.exe - 1 error(s), 0 warning(s)

Как заставить эту программу работать?
Пожалуйста, помогите мне.

Заренее благодарен.

Best regards,
Alexey

Номер выпуска : 3715
Возраст листа : 396 (дней)
Количество подписчиков : 486
Адрес в архиве : http://subscribe.ru/archive/comp.soft.prog.prog/msg/248968
Получить правила : mailto:comp.soft.prog.prog-rules@subscribe.ru
Формат "дайджест" : mailto:comp.soft.prog.prog-digest@subscribe.ru
Формат "каждое письмо" : mailto:comp.soft.prog.prog-normal@subscribe.ru
Формат "читать с веба" : mailto:comp.soft.prog.prog-webonly@subscribe.ru

-*Информационный канал Subscribe.Ru
Подписан адрес:
Код этой рассылки: comp.soft.prog.prog
Написать в лист: mailto:comp.soft.prog.prog-list@subscribe.ru
Отписаться: mailto:comp.soft.prog.prog--unsub@subscribe.ru?subject=comp.soft.prog.prog

http://subscribe.ru/ http://subscribe.ru/feedback

1. убери #include <gl/gl.h> и #include <gl/glu.h> -- они уже поключены в glut.h
2. перед функцией reverse(polygon.begin(), polygon.end()); поставь std::
3. sqrtf(..) замени на sqrt(..)
4. проверь, что у тебя есть glut.h и соответствующая glut.dll
у меня заработало после всего этого.. получилась многогранная труба с кубической
вращающейся дырой

Номер выпуска : 3716
Возраст листа : 396 (дней)
Количество подписчиков : 486
Адрес в архиве : http://subscribe.ru/archive/comp.soft.prog.prog/msg/249216
Получить правила : mailto:comp.soft.prog.prog-rules@subscribe.ru
Формат "дайджест" : mailto:comp.soft.prog.prog-digest@subscribe.ru
Формат "каждое письмо" : mailto:comp.soft.prog.prog-normal@subscribe.ru
Формат "читать с веба" : mailto:comp.soft.prog.prog-webonly@subscribe.ru

-*Информационный канал Subscribe.Ru
Подписан адрес:
Код этой рассылки: comp.soft.prog.prog
Написать в лист: mailto:comp.soft.prog.prog-list@subscribe.ru
Отписаться: mailto:comp.soft.prog.prog--unsub@subscribe.ru?subject=comp.soft.prog.prog

http://subscribe.ru/ http://subscribe.ru/feedback

Hello,

Точно! Спасибо! Чтой-то я туплю...
А еще можно было просто включить первым #include <windows>,
указать std::reverse(polygon.begin(), polygon.end()), а sqrtf можно и не трогать
Это ж у людей под Linux было и работало...
там std:: можно не указывать,
Так что вопрос скорее всего должен был звучать так:
"Помогите заставить эту программу работать под Windows"...
Спасибо еще раз!

Кстати если есть у кого-то еще какие-нибудь идеи относительно
других операций с помощью BSP (например, изменить этот код,
чтобы он строил объединение и пересечение) буду рад если сможете поделиться.

Best regards,
Alexey

Best regards,
Alexey

Номер выпуска : 3718
Возраст листа : 397 (дней)
Количество подписчиков : 486
Адрес в архиве : http://subscribe.ru/archive/comp.soft.prog.prog/msg/249600
Получить правила : mailto:comp.soft.prog.prog-rules@subscribe.ru
Формат "дайджест" : mailto:comp.soft.prog.prog-digest@subscribe.ru
Формат "каждое письмо" : mailto:comp.soft.prog.prog-normal@subscribe.ru
Формат "читать с веба" : mailto:comp.soft.prog.prog-webonly@subscribe.ru

-*Информационный канал Subscribe.Ru
Подписан адрес:
Код этой рассылки: comp.soft.prog.prog
Написать в лист: mailto:comp.soft.prog.prog-list@subscribe.ru
Отписаться: mailto:comp.soft.prog.prog--unsub@subscribe.ru?subject=comp.soft.prog.prog

http://subscribe.ru/ http://subscribe.ru/feedback

У меня довольно много информации на эту тему, но все в печатном виде.
Да и сам когда-то возился с этой штукой.
Если есть конкретные вопросы - постараюсь ответить ...

Номер выпуска : 3725
Возраст листа : 399 (дней)
Количество подписчиков : 487
Адрес в архиве : http://subscribe.ru/archive/comp.soft.prog.prog/msg/250174
Получить правила : mailto:comp.soft.prog.prog-rules@subscribe.ru
Формат "дайджест" : mailto:comp.soft.prog.prog-digest@subscribe.ru
Формат "каждое письмо" : mailto:comp.soft.prog.prog-normal@subscribe.ru
Формат "читать с веба" : mailto:comp.soft.prog.prog-webonly@subscribe.ru

-*Информационный канал Subscribe.Ru
Подписан адрес:
Код этой рассылки: comp.soft.prog.prog
Написать в лист: mailto:comp.soft.prog.prog-list@subscribe.ru
Отписаться: mailto:comp.soft.prog.prog--unsub@subscribe.ru?subject=comp.soft.prog.prog

http://subscribe.ru/ http://subscribe.ru/feedback