Busca com Coordenadas Baricêntricas - cpp, openGL.

barycentrics.md

Exercício de Programação da disciplina de Matrizes, Vetores e Geometria Analítica da EACH-USP

Aluisio Amorim

Estruturas e variáveis globais:

// estrutura para representar um ponto no plano cartesiano
typedef struct {
  double x, y;
} CartesianPoint;


// estrutura para representar um triângulo como um conjunto de três pontos
typedef struct {
  CartesianPoint a, b, c;
} Triangle;

typedef struct {
  double u, v, w;
} Barycentric;


double x_inp, y_inp;
CartesianPoint p_from_input;
Triangle triangle;
vector<int> cell_ids_to_print;

Funções auxiliares:

Barycentric barycentrics_for_p_in_triangle(CartesianPoint p, Triangle t) {
  // calcular as coordenadas baricêntricas do ponto
  double u, v, w;
  barycentric(p, t, u, v, w);

  cout<<"Coordenadas baricentricas:"<<endl;
  cout<<u<<" "<<v<<" "<<w<<endl;

  return { u, v, w };
}

Triangle get_cell_triangle(int cell_id){
	CartesianPoint p[3];
	for(int i = 0; i < 3; i++){
		double x = malha->getVertex(malha->getCell(cell_id)->getVertexId(i))->getCoord(0);
		double y = malha->getVertex(malha->getCell(cell_id)->getVertexId(i))->getCoord(1);
		p[i] = {x, y};
	}
	Triangle t = {p[0], p[1], p[2]};
	return t;
}

Funções principais:

// função para calcular as coordenadas baricêntricas de um ponto em um triângulo
void barycentric(CartesianPoint p, Triangle t, double &u, double &v, double &w) {
  // calcular os lados do triângulo
  double x0 = t.a.x, y0 = t.a.y;
  double x1 = t.b.x, y1 = t.b.y;
  double x2 = t.c.x, y2 = t.c.y;

  // calcular as coordenadas baricêntricas
  double a0 = -(x1*(p.y-y2)+x2*(y1-p.y)+(y2-y1)*p.x)/(x1*(y2-y0)+x0*(y1-y2)+x2*(y0-y1));
  double a1 = (x0*(p.y-y2)+x2*(y0-p.y)+(y2-y0)*p.x)/(x1*(y2-y0)+x0*(y1-y2)+x2*(y0-y1));
  double a2 = (x1*(p.y-y0)+x0*(y1-p.y)+(y0-y1)*p.x)/(x1*(y2-y0)+x0*(y1-y2)+x2*(y0-y1));

  // atribuir as coordenadas baricêntricas calculadas às variáveis de entrada
  u = a0;
  v = a1;
  w = a2;
}

// encontrar ponto p na malha percorrendo os triângulos recurssivamente 
void find_p(CartesianPoint p, Triangle t, int cell_id){
	cell_ids_to_print.push_back(cell_id);
	Interactor->Refresh_List();

	Barycentric b = barycentrics_for_p_in_triangle(p,t);
	double p_min = min(b.u,min(b.v,b.w));
	// para p com coordenadas baricêntricas {u, v, w} >= 0, p está contido no triângulo
	if(p_min >= 0){
		cout<<"Ponto esta dentro do triangulo"<<endl;
		cout<<"Coordenadas Baricentricas: ("<<b.u<<", "<<b.v<<", "<<b.w<<")"<<endl;

		return;
	}
	// para p com coordenadas baricêntricas negativas, o vértice de coeficiente mais negativo indica que p 
	// está na direção da aresta oposta a este vértice
	if (p_min == b.u){
		cout<<"Ponto esta na aresta bc"<<endl;
		int vertex_id = malha->getCell(cell_id)->getVertexId(0);
		int mate_cell_id = malha->getCell(cell_id)->getMateVertexId(vertex_id);

		Triangle t = get_cell_triangle(mate_cell_id);

		find_p(p, t, mate_cell_id);
	}
	else if(p_min == b.v){
		cout<<"Ponto esta na aresta ac"<<endl;
		int vertex_id = malha->getCell(cell_id)->getVertexId(1);
		int mate_cell_id = malha->getCell(cell_id)->getMateVertexId(vertex_id);
		Triangle t = get_cell_triangle(mate_cell_id);


		find_p(p, t, mate_cell_id);
	}
	else if(p_min == b.w){
		cout<<"Ponto esta na aresta ab"<<endl;
		int vertex_id = malha->getCell(cell_id)->getVertexId(2);
		int mate_cell_id = malha->getCell(cell_id)->getMateVertexId(vertex_id);

		Triangle t = get_cell_triangle(mate_cell_id);

		find_p(p, t, mate_cell_id);
	}
	else{
		cout<<"Ponto não encontrado"<<endl;
	}
}

Render Scene:

void RenderScene(void){ 
	allCommands->Execute();
	Print->Vertices(malha,blue,3);
	Print->FacesWireframe(malha,grey,3);
	for(auto it: cell_ids_to_print){
		Print->Face(it, red);
	}

	glFinish();
	glutSwapBuffers();
}

Provas de Conceito: