summaryrefslogtreecommitdiff
path: root/branches/hugues/glagen/3d/triangle.cc
diff options
context:
space:
mode:
Diffstat (limited to 'branches/hugues/glagen/3d/triangle.cc')
-rw-r--r--branches/hugues/glagen/3d/triangle.cc729
1 files changed, 0 insertions, 729 deletions
diff --git a/branches/hugues/glagen/3d/triangle.cc b/branches/hugues/glagen/3d/triangle.cc
deleted file mode 100644
index ee80216..0000000
--- a/branches/hugues/glagen/3d/triangle.cc
+++ /dev/null
@@ -1,729 +0,0 @@
-//=============================================================================
-//
-// 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 ();
-}