//***************************************************************************************** // Truevision - a 3d modeler for gnome and povray // // impsurface.cc // // Vincent LE PRINCE // Copyright (C) 2000-2001 Vincent LE PRINCE // This file is part of the TRUEVISION Package // This program is free software; you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation; either version 2 of the License, or // (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ //******************************************************************************************* #include "include/impsurface.h" #include "include/tvio.h" #include "include/preferences.h" #include "include/utils3d.h" #include #include const int type_a_edges[5][4] = {\ { 0, 1, 4, 3 },\ { 5, 1, 6, 4 },\ { 2, 1, 3, 6 },\ { 1, 3, 6, 4 },\ { 7, 6, 3, 4 } }; const int type_a_vertices[5][6] = {\ { 0, 8, 3, 12, 15, 16 },\ {9, 5, 4, 13, 17, 12},\ {1, 2, 10, 16, 14, 13},\ {16, 13, 12, 14, 17, 15},\ {6, 11, 7, 14, 15, 17} }; const int type_b_edges[5][4] = {\ { 1, 0, 2, 5 },\ { 6, 2, 7, 5 },\ { 4, 0, 5, 7 },\ { 3, 0, 7, 2 },\ { 7, 2, 0, 5 } }; const int type_b_vertices[5][6] = {\ {0, 1, 9, 16, 13, 12},\ {10, 6, 5, 14, 17, 13},\ {8, 4, 7, 12, 17, 15},\ {3, 11, 2, 15, 14, 16},\ {14, 15, 17, 16, 12, 13} }; const int edge_con_vertices[4][3] = {\ { 0, 1, 2 }, \ { 0, 5, 3 }, \ { 1, 3, 4 }, \ { 2, 4, 5 } }; const int type_a_vertices_edges[18][2] = {\ { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 0 },\ { 4, 5 }, { 5, 6 }, { 6, 7 }, { 7, 4 },\ { 0, 4 }, { 1, 5 }, { 2, 6 }, { 3, 7 },\ { 4, 1 }, { 1, 6 }, { 3, 6 }, { 3, 4 },\ { 3, 1 }, { 4, 6 } }; const int type_b_vertices_edges[18][2] = {\ { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 0 },\ { 4, 5 }, { 5, 6 }, { 6, 7 }, { 7, 4 },\ { 0, 4 }, { 1, 5 }, { 2, 6 }, { 3, 7 },\ { 0, 5 }, { 5, 2 }, { 2, 7 }, { 7, 0 },\ { 0, 2 }, { 7, 5 } }; const int alt_vertices[6][4] = {\ { 2, 1, 3, 5 },\ { 0, 2, 4, 3 },\ { 4, 5, 0, 1 },\ { 0, 5, 4, 1 },\ { 5, 2, 1, 3 },\ { 2, 4, 3, 0 } }; const int vertices_ex1[12][3][4] = {\ { { 0, 0, -1, 2 }, { 0, 1, -1, 6 }, { 0, 1, 0, 4 } },\ { { 1, 0, 0, 3 }, { 1, 1, 0, 7}, { 0, 1, 0, 5 } },\ { { 0, 0, 1, 0 }, { 0, 1, 1, 4 }, {0, 1, 0, 6 } },\ { { -1, 0, 0, 1}, { -1, 1, 0, 5}, { 0, 1, 0, 8 } },\ { { 0, -1, 0, 0}, { 0, -1, -1, 2}, { 0, 0, -1, 6 } },\ { { 0, -1, 0, 1}, { 1, -1, 0, 3}, { 1, 0, 0, 7 } },\ { { 0, -1, 0, 2}, { 0, -1, 1, 0}, { 0, 0, 1, 4 } },\ { { 0, -1, 0, 3}, { -1, -1, 0, 1}, { -1, 0, 0, 5 } },\ { { 0, 0, -1, 11}, { -1, 0, -1, 10 }, { -1, 0, 0, 9} },\ { { 1, 0, 0, 8 }, { 1, 0, -1, 11}, { 0, 0, -1, 10 } },\ { { 0, 0, 1, 9 }, { 1, 0, 1, 8 }, { 1, 0, 0, 11 } },\ { { 0, 0, 1, 8}, { -1, 0, 1, 9 }, { -1, 0, 0, 10 } } }; const int vertices_ex2[6][4] = {\ { 0, 0, -1, 14 }, { 1, 0, 0, 15 }, { 0, 0, 1, 12 }, { -1, 0, 0, 13},\ { 0, 1, 0, 17 }, { 0, -1, 0, 16 } }; bool(*Voxel::TestFunc)(gpointer, float, float, float ) = NULL; gpointer Voxel::obj = NULL; //************************************** // Voxels //************************************** void Voxel::set( int a, int b, int c, float x, float y, float z, int atype, bool(*test_func)(gpointer, float, float, float ), gpointer aobj, ImplicitSurface *surf ) { type = atype; triangles_num = 0; TestFunc = test_func; obj = aobj; coordi[0] = a; coordi[1] = b; coordi[2] = c; coordf[0] = x; coordf[1] = y; coordf[2] = z; value = test_func( obj, coordf[0], coordf[1], coordf[2] ); surface = surf; for ( int i = 0 ; i < 18 ; i++ ) vertices_intersects_calc[i] = false; } void Voxel::set_triangle( int vertices[3], int *edges_in, bool invert ) { // Calcul de l'intersection avec les bords du tetraedre for ( int vert = 0 ; vert < 3 ; vert ++ ) { int vertice = vertices[vert]; // Enregistrement du vertex triangles[triangles_num][vert] = vertice; // détermination des points if ( ! vertices_intersects_calc[vertice] ) { Voxel *edge_a, *edge_b; if ( type == VOXEL_TYPE_A ) { edge_a = edges[ type_a_vertices_edges[vertice][0] ]; edge_b = edges[ type_a_vertices_edges[vertice][1] ]; } else { edge_a = edges[ type_b_vertices_edges[vertice][0] ]; edge_b = edges[ type_b_vertices_edges[vertice][1] ]; } // calcul de l'intersection ( récursif ) float a[3], b[3]; bool a_in = ! TestFunc( obj, edge_b->coordf[0], edge_b->coordf[1], edge_b->coordf[2] ); for ( int i = 0 ; i < 3 ; i++ ) { a[i] = a_in ? edge_a->coordf[i] : edge_b->coordf[i]; b[i] = a_in ? edge_b->coordf[i] : edge_a->coordf[i]; } for ( int i = 0 ; i < IntersectRecursion ; i++ ) { float m[3]; for ( int i = 0 ; i < 3 ; i++ ) m[i] = ( a[i] + b[i] ) / 2.0; bool m_in = TestFunc( obj, m[0], m[1], m[2] ); if ( m_in ) { a[0] = m[0]; a[1] = m[1]; a[2] = m[2]; } else { b[0] = m[0]; b[1] = m[1]; b[2] = m[2]; } } for ( int i = 0 ; i < 3 ; i++ ) vertices_intersects[vertice][i] = ( a[i] + b[i] ) / 2.0; } } // Calcul de la normale au triangle float norm[3]; get_normal( vertices_intersects[vertices[0]], vertices_intersects[vertices[1]], vertices_intersects[vertices[2]], edges[edges_in[0]]->coordf, norm, invert ); float sum = sqrt( norm[0]*norm[0] + norm[1]*norm[1] + norm[2]*norm[2] ); norm[0] /= sum; norm[1] /= sum; norm[2] /= sum; // Moyenne des normales et échanges de vertex for ( int vert = 0 ; vert < 3 ; vert ++ ) { int vertice = vertices[vert]; if ( ! vertices_intersects_calc[vertice] ) { for ( int i = 0 ; i < 3 ; i++ ) vertices_intersects_norm[vertice][i] = norm[i]; vertices_intersects_norm_avg[vertice] = 1; } else { int avg = vertices_intersects_norm_avg[vertice]++; for ( int i = 0 ; i < 3 ; i++ ) vertices_intersects_norm[vertice][i] = ( norm[i] + vertices_intersects_norm[vertice][i]*avg ) / ( 1+avg ); } if ( vertice < 12 ) for ( int i = 0 ; i < 3 ; i++ ) { Voxel *vox = surface->get_voxel( coordi[0] + vertices_ex1[vertice][i][0], coordi[1] + vertices_ex1[vertice][i][1], coordi[2] + vertices_ex1[vertice][i][2] ); if ( vox != NULL ) vox->set_vertice_intersect( vertices_ex1[vertice][i][3], vertices_intersects[vertice], vertices_intersects_norm[vertice], vertices_intersects_norm_avg[vertice] ); } else { int i = vertice -12; Voxel *vox = surface->get_voxel( coordi[0] + vertices_ex2[i][0], coordi[1] + vertices_ex2[i][1], coordi[2] + vertices_ex2[i][2] ); if ( vox != NULL ) vox->set_vertice_intersect( vertices_ex2[i][3], vertices_intersects[vertice], vertices_intersects_norm[vertice], vertices_intersects_norm_avg[vertice] ); } vertices_intersects_calc[vertice] = true; } triangles_num++; } void Voxel::set_vertice_intersect( int vertice, float *coords, float *norm, int norm_avg ) { for ( int i = 0 ; i < 3 ; i++ ) { vertices_intersects[vertice][i] = coords[i]; vertices_intersects_norm[vertice][i] = norm[i]; } vertices_intersects_calc[vertice] = true; vertices_intersects_norm_avg[vertice] = norm_avg; } void Voxel::get_triangles() { int x = coordi[0] ; int y = coordi[1] ; int z = coordi[2]; Voxel * cube_edges[8] = { this, surface->get_voxel(x+1, y, z), surface->get_voxel(x+1, y, z+1), \ surface->get_voxel(x, y, z+1), surface->get_voxel(x,y-1,z), \ surface->get_voxel(x+1, y-1,z), surface->get_voxel(x+1, y-1, z+1), \ surface->get_voxel(x, y-1, z+1) }; edges = (Voxel**)cube_edges; // For each tetraedra... for ( int tetra = 0 ; tetra < 5 ; tetra++ ) { int edge_count = 0; int first_edge_in = -1; int last_edge_out = -1; int edges_in[4] = { 0, 0, 0, 0 }; int edges_in_index = 0; for ( int i = 0 ; i < 4 ; i++ ) { int index = ( type == VOXEL_TYPE_A ) ? type_a_edges[tetra][i] : type_b_edges[tetra][i] ; if ( (cube_edges[index])->value == true ) { first_edge_in = i; edge_count++; edges_in[ edges_in_index++ ] = index; } else last_edge_out = i; } switch( edge_count ) { // Every edge in or out, easy case :) Hmm doesn't need optimisation ! case 0: case 4: break; // One edge in or one edge out -> generate 1 triangle, a bit more difficult case 1: case 3: //break; { int vertices[3]; int top = ( edge_count == 1 ) ? first_edge_in : last_edge_out; if ( type == VOXEL_TYPE_A ) for ( int i = 0 ; i < 3 ; i++ ) vertices[i] = type_a_vertices[tetra][ edge_con_vertices[top][i] ]; else for ( int i = 0 ; i < 3 ; i++ ) vertices[i] = type_b_vertices[tetra][ edge_con_vertices[top][i] ]; set_triangle( vertices, edges_in, ( edge_count == 1 ) ? false : true); break; } // Two edges in -> generate 2 edges ( the worst one ! ) case 2: //break; { int vertice_in = 0; int tetra_vertices[6]; for ( int i = 0 ; i < 6 ; i++ ) tetra_vertices[i] = ( type == VOXEL_TYPE_A ) ? type_a_vertices[tetra][i] : type_b_vertices[tetra][i]; for ( int i = 0; i < 6 ; i++ ) { int edge1 = ( type == VOXEL_TYPE_A ) ? type_a_vertices_edges[ tetra_vertices[i] ][0] : type_b_vertices_edges[ tetra_vertices[i] ][0]; int edge2 = ( type == VOXEL_TYPE_A ) ? type_a_vertices_edges[ tetra_vertices[i] ][1] : type_b_vertices_edges[ tetra_vertices[i] ][1]; if ( ( edges_in[0] == edge1 && edges_in[1] == edge2 ) || ( edges_in[1] == edge1 && edges_in[0] == edge2 ) ) { vertice_in = i; break; } } int vert1 = tetra_vertices[ alt_vertices[ vertice_in ][0] ]; int vert2 = tetra_vertices[ alt_vertices[ vertice_in ][1] ]; int vert3 = tetra_vertices[ alt_vertices[ vertice_in ][2] ]; int vert4 = tetra_vertices[ alt_vertices[ vertice_in ][3] ]; int vertices1[3] = { vert1, vert2, vert4 }; int vertices2[3] = { vert2, vert4, vert3 }; set_triangle( vertices1, edges_in, false ); set_triangle( vertices2, edges_in, false ); break; } default: break; } } } void Voxel::render_triangles() { for ( int tri = 0 ; tri < triangles_num ; tri++ ) { for ( int i = 0 ; i < 3 ; i++ ) { glNormal3f( vertices_intersects_norm[ triangles[tri][i] ][0], vertices_intersects_norm[ triangles[tri][i] ][1], vertices_intersects_norm[ triangles[tri][i] ][2] ); glVertex3f( vertices_intersects[ triangles[tri][i] ][0], vertices_intersects[ triangles[tri][i] ][1], vertices_intersects[ triangles[tri][i] ][2] ); } } } //********************************************** // Implicit Surface preview object //********************************************** class VoxelGrid { public: float min[3]; float max[3]; }; //************************************** // Constructor //************************************** ImplicitSurface::ImplicitSurface( app_objs *app_ref, bool(*test_func)(gpointer, float , float , float ), gpointer aobj, float *amin, float *amax ) { //cout << "\nCalculing impsuf..."; cout.flush(); // Test function TestFunc = test_func; obj = aobj; // Set quality PREF_DEF GridSubdivision = pref->blob_preview_quality->value()+1; // Bounding box = first grid VoxelGrid *Grid0 = new VoxelGrid(); float Lmax = 0; for ( int i = 0 ; i < 3 ; i ++ ) { Grid0->min[i] = amin[i]; Grid0->max[i] = amax[i]; float test = Grid0->max[i] - Grid0->min[i]; if ( Lmax < test ) Lmax = test; } for ( int i = 0 ; i < 3 ; i++ ) { Grid0->max[i] = Grid0->min[i] + Lmax; } vector Grids; Grids.push_back( Grid0 ); // Grid tree for ( int rec = 0 ; rec < GridRecursion ; rec++ ) { vector New_Grids; for ( unsigned int i = 0 ; i < Grids.size() ; i++ ) { Lmax = Grids[i]->max[0] - Grids[i]->min[0]; float step = Lmax / GridSubdivision; float Z = Grids[i]->min[2]; for ( int z = 0 ; z < GridSubdivision ; z++ ) { float Y = Grids[i]->min[1]; for ( int y = 0 ; y < GridSubdivision ; y++ ) { float X = Grids[i]->min[0]; for ( int x = 0 ; x < GridSubdivision ; x++ ) { VoxelGrid *grid = new VoxelGrid; grid->min[0] = X; grid->min[1] = Y; grid->min[2] = Z; grid->max[0] = X+step ; grid->max[1] = Y+step; grid->max[2] = Z+step; New_Grids.push_back( grid ); X += step; } Y += step; } Z += step; } } Grids.swap( New_Grids ); New_Grids.clear(); } // Create voxels for ( unsigned int i = 0 ; i < Grids.size() ; i++ ) { Lmax = Grids[i]->max[0] - Grids[i]->min[0]; float step = Lmax / ImpSurfSubdivision; bool xalt, yalt, zalt = false; float Z = Grids[i]->min[2]-step; for ( int z = 0 ; z < ImpSurfSubdivision+3 ; z++ ) { yalt = zalt; zalt = ! zalt; float Y = Grids[i]->min[1]-step; for ( int y = 0 ; y < ImpSurfSubdivision+3 ; y++ ) { xalt = yalt; yalt = ! yalt; float X = Grids[i]->min[0]-step; for ( int x = 0 ; x < ImpSurfSubdivision+3 ; x++ ) { if ( xalt ) voxels[x][y][z].set( x, y, z, X, Y, Z, VOXEL_TYPE_A, TestFunc, obj, this ); else voxels[x][y][z].set( x, y, z, X, Y, Z, VOXEL_TYPE_B, TestFunc, obj, this ); X += step; xalt = ! xalt; } Y += step; } Z += step; } // Render triangles for ( int z = 0 ; z < ImpSurfSubdivision +2 ; z++ ) for ( int y = 1 ; y < ImpSurfSubdivision +2; y++ ) for ( int x = 0 ; x