diff options
Diffstat (limited to 'tags/START/glagen/3d/triangle.cc')
| -rw-r--r-- | tags/START/glagen/3d/triangle.cc | 729 |
1 files changed, 729 insertions, 0 deletions
diff --git a/tags/START/glagen/3d/triangle.cc b/tags/START/glagen/3d/triangle.cc new file mode 100644 index 0000000..ee80216 --- /dev/null +++ b/tags/START/glagen/3d/triangle.cc @@ -0,0 +1,729 @@ +//============================================================================= +// +// Glagen : a planet sized landscape generator +// Copyright (C) 2002 Julien Guertault, Hugues Hiegel, Meng-Tih Lam +// +// 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +// +//============================================================================= +// +// Glagen : GPL LAndscape GENerator +// +// triangle.cc for Glagen : made by Zavie (Julien Guertault) +// +// www.glagen.org +// +//============================================================================= + +#include <cmath> +#include <cstdlib> +#include "data_glagen.hh" +#include "dot.hh" +#include "misc.hh" +#include "triangle.hh" +#include "vector.hh" + +// ================================================= Constructor and destructor + +Triangle :: Triangle (Dot *a, + Dot *b, + Dot *c, + Triangle *father): + _a(a), _b(b), _c(c), + _neighbor_ab(NULL), _neighbor_bc(NULL), _neighbor_ca(NULL), + _father(father), + _child_a(NULL), _child_b(NULL), _child_c(NULL), _child_center(NULL), + _visible(true) +{ + Vector v1; + Vector v2; + + glagen.triangles = glagen.triangles + 1; + if (glagen.triangles > glagen.max_triangles) + exit (1); + if (father == NULL) + _level = 0; + else + _level = father->Level () + 1; + + a->Use (father, this); + b->Use (father, this); + c->Use (father, this); + + _center = Vector ((a->x () + b->x () + c-> x()) / 3, + (a->y () + b->y () + c-> y()) / 3, + (a->z () + b->z () + c-> z()) / 3); + + v1 = Vector (a->x () - b->x (), a->y () - b->y (), a->z () - b->z ()); + v2 = Vector (a->x () - c->x (), a->y () - c->y (), a->z () - c->z ()); + _normal = Vector (v1 ^ v2); + _size = _normal.Norm (); + _normal = _normal / _size; + _normal_real = _normal; + _size = sqrtf (_size / 2); + + step = glagen.step - 1; +} + +Triangle :: ~Triangle () +{ + if (_child_center != NULL) + { + delete _child_center; + delete _child_a; + delete _child_b; + delete _child_c; + } + + // Del the old connexity + if (_neighbor_ab != NULL) + _neighbor_ab->Del_connexity (this); + if (_neighbor_bc != NULL) + _neighbor_bc->Del_connexity (this); + if (_neighbor_ca != NULL) + _neighbor_ca->Del_connexity (this); + + // Tell the vertices they aren't used by this triangle anymore + if (_a->Drop (this, _father)) + delete _a; + if (_b->Drop (this, _father)) + delete _b; + if (_c->Drop (this, _father)) + delete _c; + + if (_father != NULL) + _father->Child_dead (this); + + glagen.triangles = glagen.triangles - 1; +} + + +// ======================================================================= Read + +// The level +unsigned int Triangle :: Level () const { return _level; } + +// The vertices +Dot *Triangle :: A () const { return _a; } +Dot *Triangle :: B () const { return _b; } +Dot *Triangle :: C () const { return _c; } + +// The neighborhood +Triangle *Triangle :: Neighbor_ab () const { return _neighbor_ab; } +Triangle *Triangle :: Neighbor_bc () const { return _neighbor_bc; } +Triangle *Triangle :: Neighbor_ca () const { return _neighbor_ca; } + +// The father +Triangle *Triangle :: Father () const { return _father; } + +// The childs +Triangle *Triangle :: Child_a() const { return _child_a; } +Triangle *Triangle :: Child_b() const { return _child_b; } +Triangle *Triangle :: Child_c() const { return _child_c; } +Triangle *Triangle :: Child_center() const { return _child_center; } +Triangle *Triangle :: Child (Dot *match) const +{ + if (match == _a) + return _child_a; + if (match == _b) + return _child_b; + if (match == _c) + return _child_c; + return NULL; +} + +Vector &Triangle :: Normal () { return _normal; } +Vector &Triangle :: Normal_real () { return _normal_real; } + +float Triangle :: Size () const { return _size; } + +// Is this triangle split ? +bool Triangle :: Is_split () const +{ + return (_child_center != NULL); +} + +// In the current turn, has this triangle been checked ? +bool Triangle :: Is_checked () const +{ + return (step == glagen.step); +} + +// According to the position of the observer, does this triangle +// need to be split ? +float Triangle :: To_split () const +{ + float x = _center.X () - glagen.observer.frame.Origin_X (); + float y = _center.Y () - glagen.observer.frame.Origin_Y (); + float z = _center.Z () - glagen.observer.frame.Origin_Z (); +// float dist = x * x + y * y + z * z; + float dist = Approx_dist(x, y, z); +// float alpha = dist / (_size * _size); + float alpha = (dist * dist) / (_size * _size); + + // Special case : + // if over the horizon, the result is increased +// if (dist > 100 * glagen.observer.altitude * glagen.observer.altitude) + if (dist > 10 * glagen.observer.altitude) + alpha = alpha * alpha / 2; +// if (dist > 1000 * glagen.observer.altitude * glagen.observer.altitude) + if (dist > 32 * glagen.observer.altitude) + alpha = alpha * alpha / 2; + if (!_visible) + alpha = (alpha * alpha) / 2; + return (alpha); +} + +// According to the position of the observer, does this triangle +// need to be merged ? +bool Triangle :: Is_visible () const { return _visible; } + +// ====================================================================== Write + +// This triangle must set a reference to the given other one +void Triangle :: Make_connexity (Triangle *neighborhood) +{ + // Find on which side is the other triangle and then set the connexity + if ((neighborhood->A () == _a) + || (neighborhood->B () == _a) + || (neighborhood->C () == _a)) + { + if ((neighborhood->A () == _b) + || (neighborhood->B () == _b) + || (neighborhood->C () == _b)) + _neighbor_ab = neighborhood; + else + _neighbor_ca = neighborhood; + } + else + _neighbor_bc = neighborhood; +} + +// This triangle must forget its reference to the given other one +void Triangle :: Del_connexity (Triangle *related) +{ + // Find the connexity and delete it + if (_neighbor_ab == related) + _neighbor_ab = NULL; + if (_neighbor_bc == related) + _neighbor_bc = NULL; + if (_neighbor_ca == related) + _neighbor_ca = NULL; +} + +// The split function +void Triangle :: Split () +{ + Dot *d; + Dot *e; + Dot *f; + Triangle *neighbor_af; + Triangle *neighbor_ae; + Triangle *neighbor_bd; + Triangle *neighbor_bf; + Triangle *neighbor_ce; + Triangle *neighbor_cd; + + // Test if the triangle is already split + if (Is_split ()) + return; + + // Check the differences of iterations + if (_neighbor_ab == NULL || _neighbor_bc == NULL || _neighbor_ca == NULL) + _father->Split_neighbor(); + + // Find / create vertex + if (_neighbor_bc->Is_split ()) + { + // Identify and save the future connexity + neighbor_bd = _neighbor_bc->Child (_b); + neighbor_cd = _neighbor_bc->Child (_c); + + // Pop the vertex to use + if (neighbor_bd->B () == neighbor_cd->C ()) + d = neighbor_bd->B (); + else + d = neighbor_bd->C (); + } + else + { + // Create the vertex and set the connexity to NULL + d = _b->Middle (_c); // new ; delete : triangle.cc l99, 101, 103 + neighbor_bd = NULL; + neighbor_cd = NULL; + } + + // The same for each side + if (_neighbor_ca->Is_split ()) + { + neighbor_ce = _neighbor_ca->Child (_c); + neighbor_ae = _neighbor_ca->Child (_a); + if (neighbor_ce->B () == neighbor_ae->C ()) + e = neighbor_ce->B (); + else + e = neighbor_ce->C (); + } + else + { + e = _c->Middle (_a); // new ; delete : triangle.cc l99, 101, 103 + neighbor_ce = NULL; + neighbor_ae = NULL; + } + + if (_neighbor_ab->Is_split ()) + { + neighbor_af = _neighbor_ab->Child (_a); + neighbor_bf = _neighbor_ab->Child (_b); + if (neighbor_af->B () == neighbor_bf->C ()) + f = neighbor_af->B (); + else + f = neighbor_af->C (); + } + else + { + f = _a->Middle (_b); // new ; delete : triangle.cc l99, 101, 103 + neighbor_af = NULL; + neighbor_bf = NULL; + } + + // Create triangles + _child_center = new Triangle (d, e, f, this); // delete : triangle.cc l90 + _child_a = new Triangle (_a, f, e, this); // delete : triangle.cc l91 + _child_b = new Triangle (_b, d, f, this); // delete : triangle.cc l92 + _child_c = new Triangle (_c, e, d, this); // delete : triangle.cc l93 + + // Set the final connexity + if (neighbor_af != NULL) + { + _child_a->Make_connexity (neighbor_af); + neighbor_af->Make_connexity (_child_a); + } + if (neighbor_ae != NULL) + { + _child_a->Make_connexity (neighbor_ae); + neighbor_ae->Make_connexity (_child_a); + } + if (neighbor_bd != NULL) + { + _child_b->Make_connexity (neighbor_bd); + neighbor_bd->Make_connexity (_child_b); + } + if (neighbor_bf != NULL) + { + _child_b->Make_connexity (neighbor_bf); + neighbor_bf->Make_connexity (_child_b); + } + if (neighbor_ce != NULL) + { + _child_c->Make_connexity (neighbor_ce); + neighbor_ce->Make_connexity (_child_c); + } + if (neighbor_cd != NULL) + { + _child_c->Make_connexity (neighbor_cd); + neighbor_cd->Make_connexity (_child_c); + } + + _child_a->Make_connexity (_child_center); + _child_b->Make_connexity (_child_center); + _child_c->Make_connexity (_child_center); + _child_center->Make_connexity (_child_a); + _child_center->Make_connexity (_child_b); + _child_center->Make_connexity (_child_c); + + // Check for chained reactions + if (_neighbor_ab != NULL) + _neighbor_ab->Check_T (); + if (_neighbor_bc != NULL) + _neighbor_bc->Check_T (); + if (_neighbor_ca != NULL) + _neighbor_ca->Check_T (); +} + +// Check if a triangle needs to be split just because too many +// triangles in the neighborhood are split. +void Triangle :: Check_T () +{ + int warning; + + // The T problem only occurs if the triangle isn't Split + if (_child_center != NULL) + return; + warning = 0; + if (_neighbor_ab != NULL) + if (_neighbor_ab->Is_split ()) + warning = warning + 1; + if (_neighbor_bc != NULL) + if (_neighbor_bc->Is_split ()) + warning = warning + 1; + if (_neighbor_ca != NULL) + if (_neighbor_ca->Is_split ()) + warning = warning + 1; + if (warning > 1) + Split (); +} + +// The big merging function : we are not sure it will really merge +// the triangle, but at least, it will merge the children. +void Triangle :: Merge () +{ + unsigned char i; + + if (Is_split()) + { + // First we merge the children + _child_center->Merge_simple (); + _child_a->Merge_simple (); + _child_b->Merge_simple (); + _child_c->Merge_simple (); + + // Then we check the neighborhood + i = 0; + if (_neighbor_ab != NULL) + if (_neighbor_ab->Is_split ()) + { + _neighbor_ab->Front_attack (_a, _b); + i = i + 1; + } + if (_neighbor_bc != NULL) + if (_neighbor_bc->Is_split ()) + { + _neighbor_bc->Front_attack (_b, _c); + i = i + 1; + } + if (_neighbor_ca != NULL) + if (_neighbor_ca->Is_split ()) + { + _neighbor_ca->Front_attack (_c, _a); + i = i + 1; + } + + // If there's only one split neighbor triangle, then we can + // also destroy the children. Else we can't because it would + // have too much unexpected effects + if (i < 2) + { + // Destroy the child + delete _child_center; + delete _child_a; + delete _child_b; + delete _child_c; + + // Don't forget to change the pointers ! + _child_center = NULL; + _child_a = NULL; + _child_b = NULL; + _child_c = NULL; + } + } +} + +// Just a merge function without T case management +void Triangle :: Merge_simple () +{ + if (_child_center != NULL) + { + // Recursive merge + _child_center->Merge_simple (); + _child_a->Merge_simple (); + _child_b->Merge_simple (); + _child_c->Merge_simple (); + + // Destroy the child + delete _child_center; + delete _child_a; + delete _child_b; + delete _child_c; + + // Don't forget to change the pointers ! + _child_center = NULL; + _child_a = NULL; + _child_b = NULL; + _child_c = NULL; + } +} + +// Check the triangle for T cases when the neigbor triangle is merged +void Triangle :: Front_attack (Dot *quad_a, Dot *quad_d) +{ + Dot *quad_b; + Dot *quad_c; + Triangle *triangle_ab; + Triangle *triangle_cd; + Triangle *last_child; + + triangle_ab = Child (quad_a); + triangle_cd = Child (quad_d); + if (quad_a == _a) + { + if (quad_d == _b) + last_child = _child_c; + else + last_child = _child_b; + } + else + if (quad_a == _b) + { + if (quad_d == _c) + last_child = _child_a; + else + last_child = _child_c; + } + else + if (quad_d == _a) + last_child = _child_b; + else + last_child = _child_a; + + triangle_ab->Merge_simple (); + _child_center->Merge_simple (); + triangle_cd->Merge_simple (); + + if (triangle_ab->B () == triangle_cd->C ()) + { + quad_b = triangle_ab->C (); + quad_c = triangle_cd->B (); + if (triangle_ab->Neighbor_ca () != NULL) + if (triangle_ab->Neighbor_ca ()->Is_split ()) + triangle_ab->Neighbor_ca ()->Front_attack (quad_a, quad_b); + if (triangle_cd->Neighbor_ab () != NULL) + if (triangle_cd->Neighbor_ab ()->Is_split ()) + triangle_cd->Neighbor_ab ()->Front_attack (quad_c, quad_d); + } + else + { + quad_b = triangle_ab->B (); + quad_c = triangle_cd->C (); + if (triangle_ab->Neighbor_ab () != NULL) + if (triangle_ab->Neighbor_ab ()->Is_split ()) + triangle_ab->Neighbor_ab ()->Front_attack (quad_a, quad_b); + if (triangle_cd->Neighbor_ca () != NULL) + if (triangle_cd->Neighbor_ca ()->Is_split ()) + triangle_cd->Neighbor_ca ()->Front_attack (quad_c, quad_d); + } + if (last_child->Is_split ()) + last_child->Front_attack (quad_b, quad_c); +} + +// Check all the triangles to apply split or merge +void Triangle :: Split_visitor () +{ + if (step == glagen.step) + return; + step = glagen.step; + + float to_split = To_split (); + + if (to_split != 0) + { + if (to_split > 350) + Merge (); + else + { + if (glagen.triangles <= glagen.max_triangles) + if (to_split < 300) + if (false == Is_split ()) + Split (); + + if (Is_split ()) + { + // We check the childs + _child_center->Split_visitor (); + _child_a->Split_visitor (); + _child_b->Split_visitor (); + _child_c->Split_visitor (); + } + } + } + + // If there's no father, it means it's one of the root + // triangles and we can go to check the neighborhood + if (NULL == _father) + { + _neighbor_ab->Split_visitor (); + _neighbor_bc->Split_visitor (); + _neighbor_ca->Split_visitor (); + } +} + +// The visitor that computes if a triangle is visible or not. +bool Triangle :: Hide_visitor () +{ + if (step != glagen.step) + { + step = glagen.step; + if (Is_split ()) + { + _visible = _child_a->Hide_visitor (); + _visible = _child_b->Hide_visitor () || _visible; + _visible = _child_c->Hide_visitor () || _visible; + _visible = _child_center->Hide_visitor () || _visible; + } + else + { + // Let compute if it is visible... + + // We construct the vector from the center of to planet to + // the observer + Vector v = Vector (glagen.observer.frame.Origin_X () - _center.X (), + glagen.observer.frame.Origin_Y () - _center.Y (), + glagen.observer.frame.Origin_Z () - + _center.Z ()); + // We compute the scalar product to know how far it is + _visible = ((_normal * v) > 0); + + // Now, let compute if it is in the vision field + if (_visible == true) + { + v.Approx_normalize (); + _visible = (v * glagen.observer.frame.Basis_Z () < -0.70); + } + } + + // If there's no father, it means it's one of the root + // triangles and we can go to check the neighborhood + if (NULL == _father) + { + _neighbor_ab->Hide_visitor (); + _neighbor_bc->Hide_visitor (); + _neighbor_ca->Hide_visitor (); + } + } + return _visible; +} + +// Called by a child when deleted +void Triangle :: Child_dead (Triangle *child) +{ + if (_child_center == child) + _child_center = NULL; + if (_child_a == child) + _child_a = NULL; + if (_child_b == child) + _child_b = NULL; + if (_child_c == child) + _child_c = NULL; +} + +// This triangle is checked +void Triangle :: Checked () { step = glagen.step; } + + +// ====================================================================== Other + +// Split the neighborhood triangles +void Triangle :: Split_neighbor () +{ + if (_neighbor_ab != NULL) + _neighbor_ab->Split (); + if (_neighbor_bc != NULL) + _neighbor_bc->Split (); + if (_neighbor_ca != NULL) + _neighbor_ca->Split (); +} + +// Update the normal vector, if the triangle is moving. +void Triangle :: Update_normal () +{ + surface_t *surface; + float adjust = 0; + + // Get the position of the dot A + if (glagen.display_planet == true) + { + if (NULL == _a->Property (0)) + adjust = 0; + else + { + surface = static_cast <surface_t *> (_a->Property (0)->data); + if (NULL == surface) + adjust = 0; + else + adjust = surface->height; + } + } + float ax = _a->x () * (glagen.size + adjust); + float ay = _a->y () * (glagen.size + adjust); + float az = _a->z () * (glagen.size + adjust); + + // Get the position of the dot B + if (glagen.display_planet) + { + if (NULL == _b->Property (0)) + adjust = 0; + else + { + surface = static_cast <surface_t *> (_b->Property (0)->data); + if (NULL == surface) + adjust = 0; + else + adjust = surface->height; + } + } + float bx = _b->x () * (glagen.size + adjust); + float by = _b->y () * (glagen.size + adjust); + float bz = _b->z () * (glagen.size + adjust); + + // Get the position of the dot C + if (glagen.display_planet) + { + if (NULL == _c->Property (0)) + adjust = 0; + else + { + surface = static_cast <surface_t *> (_c->Property (0)->data); + if (NULL == surface) + adjust = 0; + else + adjust = surface->height; + } + } + float cx = _c->x () * (glagen.size + adjust); + float cy = _c->y () * (glagen.size + adjust); + float cz = _c->z () * (glagen.size + adjust); + + Vector v1 = Vector (ax - bx, ay - by, az - bz); + Vector v2 = Vector (ax - cx, ay - cy, az - cz); + _normal_real = Vector (v1 ^ v2); + _normal_real.Normalize (); +} + +void Triangle :: Update_normal_visitor () +{ + if (step == glagen.step) + return; + step = glagen.step; + + Update_normal (); + + if (_child_center != NULL) + { + _child_center->Update_normal_visitor (); + _child_a->Update_normal_visitor (); + _child_b->Update_normal_visitor (); + _child_c->Update_normal_visitor (); + } + + if (NULL == _father) + { + _neighbor_ab->Update_normal_visitor (); + _neighbor_bc->Update_normal_visitor (); + _neighbor_ca->Update_normal_visitor (); + } + + _a->Update_normal (); + _b->Update_normal (); + _c->Update_normal (); +} |