root/OpenSceneGraph/trunk/src/osgUtil/DelaunayTriangulator.cpp @ 12597

Revision 12597, 55.8 kB (checked in by robert, 3 years ago)

Resolved warnings reported by g++ 4.6's -Wunused-but-set-variable.

Warnings were:

/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osg/ShapeDrawable.cpp: In member function ‘void PrimitiveShapeVisitor::createHalfSphere(unsigned int, unsigned int, float, int, float, const Matrix&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osg/ShapeDrawable.cpp:1409:11: warning: variable ‘nzBase’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osg/ShapeDrawable.cpp:1410:11: warning: variable ‘nRatioBase’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgUtil/DelaunayTriangulator.cpp: In function ‘osgUtil::Triangle_list osgUtil::fillHole(osg::Vec3Array*, std::vector<unsigned int, std::allocator<unsigned int> >)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgUtil/DelaunayTriangulator.cpp:569:27: warning: variable ‘ptest’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgUtil/DelaunayTriangulator.cpp: In member function ‘bool osgUtil::DelaunayTriangulator::triangulate()’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgUtil/DelaunayTriangulator.cpp:979:45: warning: variable ‘curp’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgUtil/RenderStage.cpp: In member function ‘void osgUtil::RenderStage::runCameraSetUp(osg::RenderInfo?&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgUtil/RenderStage.cpp:631:18: warning: variable ‘stencilAttached’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgText/FadeText.cpp: In member function ‘void FadeTextPolytopeData::buildPolytope()’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgText/FadeText.cpp:74:20: warning: variable ‘edge23’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgText/FadeText.cpp:75:20: warning: variable ‘edge30’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgText/Text.cpp: In member function ‘void osgText::Text::computeBackdropPositions(unsigned int) const’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgText/Text.cpp:747:10: warning: variable ‘is_valid_size’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgGA/NodeTrackerManipulator.cpp: In member function ‘virtual bool osgGA::NodeTrackerManipulator::performMovementLeftMouseButton(double, double, double)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgGA/NodeTrackerManipulator.cpp:257:21: warning: variable ‘lookVector’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgGA/NodeTrackerManipulator.cpp:259:21: warning: variable ‘upVector’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgGA/TerrainManipulator.cpp: In member function ‘virtual bool osgGA::TerrainManipulator::performMovementMiddleMouseButton(double, double, double)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgGA/TerrainManipulator.cpp:217:11: warning: variable ‘lookVector’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgGA/TerrainManipulator.cpp:219:11: warning: variable ‘upVector’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgVolume/FixedFunctionTechnique.cpp: In member function ‘virtual void osgVolume::FixedFunctionTechnique::init()’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgVolume/FixedFunctionTechnique.cpp:124:30: warning: variable ‘tf’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgParticle/FluidProgram.cpp: In member function ‘virtual void osgParticle::FluidProgram::execute(double)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgParticle/FluidProgram.cpp:38:23: warning: variable ‘velBefore’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgShadow/ParallelSplitShadowMap.cpp: In member function ‘virtual void osgShadow::ParallelSplitShadowMap::cull(osgUtil::CullVisitor?&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgShadow/ParallelSplitShadowMap.cpp:593:22: warning: variable ‘bb’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgTerrain/GeometryTechnique.cpp: In member function ‘virtual void osgTerrain::GeometryTechnique::generateGeometry(osgTerrain::GeometryTechnique::BufferData?&, osgTerrain::Locator*, const osg::Vec3d&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgTerrain/GeometryTechnique.cpp:777:12: warning: variable ‘i_sampleFactor’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgTerrain/GeometryTechnique.cpp:778:12: warning: variable ‘j_sampleFactor’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/dds/ReaderWriterDDS.cpp: In function ‘osg::Image* ReadDDSFile(std::istream&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/dds/ReaderWriterDDS.cpp:314:10: warning: variable ‘is3dImage’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/dds/ReaderWriterDDS.cpp: In function ‘bool WriteDDSFile(const osg::Image*, std::ostream&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/dds/ReaderWriterDDS.cpp:721:10: warning: variable ‘is3dImage’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/hdr/hdrloader.cpp: In static member function ‘static bool HDRLoader::load(const char*, bool, HDRLoaderResult&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/hdr/hdrloader.cpp:101:10: warning: variable ‘cmd’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/vtf/ReaderWriterVTF.cpp: In function ‘osg::Image* ReadVTFFile(std::istream&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/vtf/ReaderWriterVTF.cpp:360:23: warning: variable ‘base’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/jp2/ReaderWriterJP2.cpp: In function ‘int putdata(jas_stream_t*, jas_image_t*, int)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/jp2/ReaderWriterJP2.cpp:41:13: warning: variable ‘linelen’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/Inventor/ConvertToInventor.cpp: In member function ‘void ConvertToInventor::processGeometry(const osg::Geometry*, ConvertToInventor::InventorState?*)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/Inventor/ConvertToInventor.cpp:1639:10: warning: variable ‘ok’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/Inventor/ConvertFromInventor.cpp: In member function ‘virtual SbBool? SoVRMLImageTextureOsg::readInstance(SoInput?*, short unsigned int)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/Inventor/ConvertFromInventor.cpp:1264:16: warning: variable ‘retval’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/OpenFlight/GeometryRecords.cpp: In member function ‘virtual void flt::Face::readRecord(flt::RecordInputStream?&, flt::Document&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/OpenFlight/GeometryRecords.cpp:369:19: warning: variable ‘secondaryPackedColor’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/OpenFlight/GeometryRecords.cpp: In member function ‘virtual void flt::Mesh::readRecord(flt::RecordInputStream?&, flt::Document&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/OpenFlight/GeometryRecords.cpp:942:19: warning: variable ‘secondaryPackedColor’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/OpenFlight/ReaderWriterFLT.cpp: In member function ‘virtual osgDB::ReaderWriter::ReadResult? FLTReaderWriter::readNode(std::istream&, const Options*) const’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/OpenFlight/ReaderWriterFLT.cpp:427:40: warning: variable ‘pos’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/ive/ShapeAttributeList.cpp: In member function ‘void ive::ShapeAttributeList::write(ive::DataOutputStream?*)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/ive/ShapeAttributeList.cpp:31:48: warning: variable ‘it’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/ac/Geode.cpp: In member function ‘void ac3d::Geode::ProcessGeometry?(std::ostream&, unsigned int)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/ac/Geode.cpp:806:35: warning: variable ‘fRep_s’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/ac/Geode.cpp:806:43: warning: variable ‘fRep_t’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/ac/Geode.cpp:807:35: warning: variable ‘fOffset_s’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/ac/Geode.cpp:807:46: warning: variable ‘fOffset_t’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/ac/Geode.cpp:932:38: warning: variable ‘primLength’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/txp/trpage_geom.cpp: In member function ‘virtual bool trpgGeometry::Write(trpgWriteBuffer&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/txp/trpage_geom.cpp:615:19: warning: variable ‘u’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/txp/trpage_material.cpp: In member function ‘int trpgMatTable::AddMaterial?(const trpgMaterial&, bool)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/txp/trpage_material.cpp:103:10: warning: variable ‘spaceInTable’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/txp/trpage_rarchive.cpp: In member function ‘virtual bool trpgr_Archive::ReadHeader?(bool)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/txp/trpage_rarchive.cpp:261:14: warning: variable ‘headerHasTexTable’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/zip/unzip.cpp: In member function ‘ZRESULT TUnzip::Get(int, ZIPENTRY*)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/zip/unzip.cpp:4055:8: warning: variable ‘hidden’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/zip/unzip.cpp:4055:22: warning: variable ‘system’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/zip/unzip.cpp:4055:36: warning: variable ‘archive’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/zip/ZipArchive.cpp: In member function ‘virtual bool ZipArchive::getFileNames(osgDB::Archive::FileNameList?&) const’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/zip/ZipArchive.cpp:91:37: warning: variable ‘iterEnd’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/pvr/ReaderWriterPVR.cpp: In member function ‘osgDB::ReaderWriter::ReadResult? ReaderWriterPVR::readPVRStream(std::istream&) const’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/pvr/ReaderWriterPVR.cpp:155:14: warning: variable ‘hasAlpha’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgViewer/View.cpp: In function ‘osg::Geometry* create3DSphericalDisplayDistortionMesh(const Vec3&, const Vec3&, const Vec3&, double, double, osg::Image*, const Matrix&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgViewer/View.cpp:737:15: warning: variable ‘cursor’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgViewer/View.cpp: In function ‘osg::Geometry* createParoramicSphericalDisplayDistortionMesh(const Vec3&, const Vec3&, const Vec3&, double, double, osg::Image*, const Matrix&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgViewer/View.cpp:1130:19: warning: variable ‘cursor’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgViewer/View.cpp:1118:15: warning: variable ‘dx’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgViewer/GraphicsWindowX11.cpp: In member function ‘virtual void osgViewer::GraphicsWindowX11::checkEvents()’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgViewer/GraphicsWindowX11.cpp:1181:10: warning: variable ‘destroyWindowRequested’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/cfg/ConfigParser.cpp: In member function ‘bool osgProducer::CameraConfig::parseFile(const string&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/cfg/ConfigParser.cpp:2247:13: warning: variable ‘result’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgQt/QGraphicsViewAdapter.cpp: In member function ‘bool osgQt::QGraphicsViewAdapter::handlePointerEvent(int, int, int)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgQt/QGraphicsViewAdapter.cpp:344:17: warning: variable ‘viewportGeometry’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgdistortion/osgdistortion.cpp: In function ‘osg::Node* createDistortionSubgraph(osg::Node*, const Vec4&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgdistortion/osgdistortion.cpp:125:19: warning: variable ‘cursor’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgdistortion/osgdistortion.cpp:126:19: warning: variable ‘texcoord’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgdistortion/osgdistortion.cpp: In function ‘osg::Geometry* createDomeDistortionMesh(const Vec3&, const Vec3&, const Vec3&, osg::ArgumentParser?&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgdistortion/osgdistortion.cpp:358:15: warning: variable ‘cursor’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgposter/osgposter.cpp: In function ‘int main(int, char**)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgposter/osgposter.cpp:253:31: warning: variable ‘outputTiles’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgthreadedterrain/osgthreadedterrain.cpp: In function ‘int main(int, char**)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgthreadedterrain/osgthreadedterrain.cpp:669:10: warning: variable ‘readParameter’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgtext3D/TextNode.cpp: In member function ‘virtual void osgText::Layout::layout(osgText::TextNode?&) const’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgtext3D/TextNode.cpp:80:11: warning: variable ‘characterHeightScale’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgvolume/osgvolume.cpp: In function ‘int main(int, char**)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgvolume/osgvolume.cpp:678:38: warning: variable ‘internalFormatMode’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgwidgetcanvas/osgwidgetcanvas.cpp: In function ‘bool windowMouseOver(osgWidget::Event&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgwidgetcanvas/osgwidgetcanvas.cpp:27:24: warning: variable ‘xy’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgwidgetcanvas/osgwidgetcanvas.cpp: In function ‘bool widgetMouseOver(osgWidget::Event&)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/examples/osgwidgetcanvas/osgwidgetcanvas.cpp:35:24: warning: variable ‘xy’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/p3d/ReaderWriterP3D.cpp: In member function ‘osg::Node* ReaderWriterP3DXML::parseXmlGraph(osgDB::XmlNode?*, bool, osgDB::Options*) const’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/src/osgPlugins/p3d/ReaderWriterP3D.cpp:2121:10: warning: variable ‘readSlide’ set but not used [-Wunused-but-set-variable]
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/applications/present3D/present3D.cpp: In function ‘int main(int, char**)’:
/home/stephan/Dev/LibSources/OpenSceneGraph-3.0.0-rc2/applications/present3D/present3D.cpp:639:10: warning: variable ‘sizesSpecified’ set but not used [-Wunused-but-set-variable]

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
Line 
1/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
2 *
3 * This library is open source and may be redistributed and/or modified under 
4 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
5 * (at your option) any later version.  The full license is in LICENSE file
6 * included with this distribution, and on the openscenegraph.org website.
7 *
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11 * OpenSceneGraph Public License for more details.
12*/
13
14#include <osgUtil/DelaunayTriangulator>
15// NB this algorithm makes heavy use of the osgUtil::Tessellator for constrained triangulation.
16// truly it is built on the shoulders of giants.
17
18#include <osg/GL>
19#include <osg/Vec3>
20#include <osg/Array>
21#include <osg/Notify>
22
23#include <algorithm>
24#include <set>
25#include <map> //GWM July 2005 map is used in constraints.
26#include <osgUtil/Tessellator> // tessellator triangulates the constrained triangles
27#include <stdlib.h>
28#include <iterator>
29
30namespace osgUtil
31{
32
33//////////////////////////////////////////////////////////////////////////////////////
34// MISC MATH FUNCTIONS
35
36
37// Compute the circumcircle of a triangle (only x and y coordinates are used),
38// return (Cx, Cy, r^2)
39inline osg::Vec3 compute_circumcircle(
40    const osg::Vec3 &a,
41    const osg::Vec3 &b,
42    const osg::Vec3 &c)
43{
44    float D =
45        (a.x() - c.x()) * (b.y() - c.y()) -
46        (b.x() - c.x()) * (a.y() - c.y());
47
48    float cx, cy, r2;
49
50    if(D==0.0)
51    {
52        // (Nearly) degenerate condition - either two of the points are equal (which we discount)
53        // or the three points are colinear. In this case we just determine the average of
54        // the three points as the centre for correctness, but squirt out a zero radius.
55        // This method will produce a triangulation with zero area, so we have to check later
56        cx = (a.x()+b.x()+c.x())/3.0;
57        cy = (a.y()+b.y()+c.y())/3.0;
58        r2 = 0.0;
59    }
60    else
61    {
62        cx =
63        (((a.x() - c.x()) * (a.x() + c.x()) +
64        (a.y() - c.y()) * (a.y() + c.y())) / 2 * (b.y() - c.y()) -
65        ((b.x() - c.x()) * (b.x() + c.x()) +
66        (b.y() - c.y()) * (b.y() + c.y())) / 2 * (a.y() - c.y())) / D;
67
68        cy =
69        (((b.x() - c.x()) * (b.x() + c.x()) +
70        (b.y() - c.y()) * (b.y() + c.y())) / 2 * (a.x() - c.x()) -
71        ((a.x() - c.x()) * (a.x() + c.x()) +
72        (a.y() - c.y()) * (a.y() + c.y())) / 2 * (b.x() - c.x())) / D;
73
74      //  r2 = (c.x() - cx) * (c.x() - cx) + (c.y() - cy) * (c.y() - cy);
75        // the return r square is compared with r*r many times in an inner loop
76        // so for efficiency use the inefficient sqrt once rather than 30* multiplies later.
77        r2 = sqrt((c.x() - cx) * (c.x() - cx) + (c.y() - cy) * (c.y() - cy));
78    }
79    return osg::Vec3(cx, cy, r2);
80}
81
82// Test whether a point (only the x and y coordinates are used) lies inside
83// a circle; the circle is passed as a vector: (Cx, Cy, r).
84
85inline bool point_in_circle(const osg::Vec3 &point, const osg::Vec3 &circle)
86{
87    float r2 =
88        (point.x() - circle.x()) * (point.x() - circle.x()) +
89        (point.y() - circle.y()) * (point.y() - circle.y());
90    return r2 <= circle.z()*circle.z();
91//    return r2 <= circle.z();
92}
93
94
95//
96//////////////////////////////////////////////////////////////////////////////////////
97
98
99// data type for vertex indices
100typedef GLuint Vertex_index;
101
102
103// CLASS: Edge
104// This class describes an edge of a triangle (it stores vertex indices to the two
105// endpoints).
106
107class Edge {
108public:
109
110    // Comparison object (for sorting)
111    struct Less
112    {
113        inline bool operator()(const Edge &e1, const Edge &e2) const
114        {
115            if (e1.ibs() < e2.ibs()) return true;
116            if (e1.ibs() > e2.ibs()) return false;
117            if (e1.ies() < e2.ies()) return true;
118            return false;
119        }
120    };
121
122    Edge(): ib_(0), ie_(0), ibs_(0), ies_(0), duplicate_(false) {}
123    Edge(Vertex_index ib, Vertex_index ie) : ib_(ib), ie_(ie), ibs_(osg::minimum(ib, ie)), ies_(osg::maximum(ib, ie)), duplicate_(false) {}
124
125    // first endpoint
126    inline Vertex_index ib() const { return ib_; }
127
128    // second endpoint
129    inline Vertex_index ie() const { return ie_; }
130
131    // first sorted endpoint
132    inline Vertex_index ibs() const { return ibs_; }
133
134    // second sorted endpoint
135    inline Vertex_index ies() const { return ies_; }
136
137    // get the "duplicate" flag
138    inline bool get_duplicate() const { return duplicate_; }
139
140    // set the "duplicate" flag
141    inline void set_duplicate(bool v) { duplicate_ = v; }
142
143private:
144    Vertex_index ib_, ie_;
145    Vertex_index ibs_, ies_;
146    bool duplicate_;
147};
148
149
150// CLASS: Triangle
151
152class Triangle
153{
154public:
155
156    Triangle():
157        a_(0),
158        b_(0),
159        c_(0) {}
160       
161   
162    Triangle(Vertex_index a, Vertex_index b, Vertex_index c, osg::Vec3Array *points)
163        :    a_(a),
164            b_(b),
165            c_(c),
166            cc_(compute_circumcircle((*points)[a_], (*points)[b_], (*points)[c_]))
167    {
168        edge_[0] = Edge(a_, b_);
169        edge_[1] = Edge(b_, c_);
170        edge_[2] = Edge(c_, a_);
171    }
172
173    Triangle& operator = (const Triangle& rhs)
174    {
175        if (&rhs==this) return *this;
176       
177        a_ = rhs.a_;
178        b_ = rhs.b_;
179        c_ = rhs.c_;
180        cc_ = rhs.cc_;
181        edge_[0]  = rhs.edge_[0];
182        edge_[1]  = rhs.edge_[1];
183        edge_[2]  = rhs.edge_[2];
184       
185        return *this;
186    }
187
188    inline Vertex_index a() const { return a_; }
189    inline Vertex_index b() const { return b_; }
190    inline Vertex_index c() const { return c_; }
191    inline void incrementa(const int delta) { a_+=delta; }
192    inline void incrementb(const int delta) { b_+=delta; }
193    inline void incrementc(const int delta) { c_+=delta; }
194
195    inline const Edge &get_edge(int idx) const { return edge_[idx];    }
196    inline const osg::Vec3 &get_circumcircle() const { return cc_; }
197
198    inline osg::Vec3 compute_centroid(const osg::Vec3Array *points) const
199    {
200        return ((*points)[a_] +(*points)[b_] + (*points)[c_])/3;
201    }
202
203    inline osg::Vec3 compute_normal(osg::Vec3Array *points) const
204    {
205        osg::Vec3 N = ((*points)[b_] - (*points)[a_]) ^ ((*points)[c_] - (*points)[a_]);
206        return N / N.length();
207    }
208
209    bool isedge(const unsigned int ip1,const unsigned int ip2) const
210    { // is one of the edges of this triangle from ip1-ip2
211        bool isedge=ip1==a() && ip2==b();
212        if (!isedge)
213        {
214            isedge=ip1==b() && ip2==c();
215            if (!isedge)
216            {
217                isedge=ip1==c() && ip2==a();
218            }
219        }
220        return isedge;
221    }
222    // GWM July 2005 add test for triangle intersected by p1-p2.
223    // return true for unused edge
224
225    const bool intersected(const unsigned int ip1,const unsigned int ip2,const osg::Vec2 p1 ,const osg::Vec2 p2,const int iedge, osg::Vec3Array *points) const
226    {
227        // return true if edge iedge of triangle is intersected by ip1,ip2
228        Vertex_index ie1,ie2;
229        if (iedge==0)
230        {
231            ie1=a();
232            ie2=b();
233        }
234        else if (iedge==1)
235        {
236            ie1=b();
237            ie2=c();
238        }
239        else if (iedge==2)
240        {
241            ie1=c();
242            ie2=a();
243        }
244        if (ip1==ie1 || ip2==ie1) return false;
245        if (ip1==ie2 || ip2==ie2) return false;
246   
247        osg::Vec2 tp1((*points)[ie1].x(),(*points)[ie1].y());
248        osg::Vec2 tp2((*points)[ie2].x(),(*points)[ie2].y());
249        return intersect(tp1,tp2,p1,p2);
250    }
251   
252    bool intersectedby(const osg::Vec2 p1,const osg::Vec2 p2,osg::Vec3Array *points) const {
253        // true if line [p1,p2] cuts at least one edge of this triangle
254        osg::Vec2 tp1((*points)[a()].x(),(*points)[a()].y());
255        osg::Vec2 tp2((*points)[b()].x(),(*points)[b()].y());
256        osg::Vec2 tp3((*points)[c()].x(),(*points)[c()].y());
257        bool ip=intersect(tp1,tp2,p1,p2);
258        if (!ip)
259        {
260            ip=intersect(tp2,tp3,p1,p2);
261            if (!ip)
262            {
263                ip=intersect(tp3,tp1,p1,p2);
264            }
265        }
266        return ip;
267    }
268    int whichEdge(osg::Vec3Array *points,const osg::Vec2 p1, const osg::Vec2 p2,
269        const unsigned int e1,const unsigned int e2) const
270    {
271        int icut=0;
272        // find which edge of triangle is cut by line (p1-p2) and is NOT e1-e2 indices.
273        // return 1 - cut is on edge b-c; 2==c-a
274        osg::Vec2 tp1((*points)[a()].x(),(*points)[a()].y()); // triangle vertices
275        osg::Vec2 tp2((*points)[b()].x(),(*points)[b()].y());
276        osg::Vec2 tp3((*points)[c()].x(),(*points)[c()].y());
277        bool ip=intersect(tp2,tp3,p1,p2);
278        if (ip && (a()==e1 || a()==e2)) { return 1;}
279        ip=intersect(tp3,tp1,p1,p2);
280        if (ip && (b()==e1 || b()==e2)) { return 2;}
281        ip=intersect(tp1,tp2,p1,p2);
282        if (ip && (c()==e1 || c()==e2)) { return 3;}
283        return icut;
284    }
285
286    bool usesVertex(const unsigned int ip) const
287    {
288        return ip==a_ || ip==b_ || ip==c_;
289    }
290
291    int lineBisectTest(const osg::Vec3 apt,const osg::Vec3 bpt,const osg::Vec3 cpt, const osg::Vec2 p2) const
292    {
293        osg::Vec2 vp2tp=p2-osg::Vec2(apt.x(), apt.y()); // vector from p1 to a.
294        // test is: cross product (z component) with ab,ac is opposite signs
295        // AND dot product with ab,ac has at least one positive value.
296        osg::Vec2 vecba=osg::Vec2(bpt.x(), bpt.y())-osg::Vec2(apt.x(), apt.y());
297        osg::Vec2 vecca=osg::Vec2(cpt.x(), cpt.y())-osg::Vec2(apt.x(), apt.y());
298        float cprodzba=vp2tp.x()*vecba.y() - vp2tp.y()*vecba.x();
299        float cprodzca=vp2tp.x()*vecca.y() - vp2tp.y()*vecca.x();
300    //    OSG_WARN << "linebisect test " << " tri " << a_<<","<< b_<<","<< c_<<std::endl;
301        if (cprodzba*cprodzca<0)
302        {
303            // more tests - check dot products are at least partly parallel to test line.
304            osg::Vec2 tp1(bpt.x(),bpt.y()); // triangle vertices
305            osg::Vec2 tp2(cpt.x(),cpt.y());
306            osg::Vec2 tp3(apt.x(),apt.y());
307            bool ip=intersect(tp1,tp2,tp3,p2);
308            if (ip) return 1;
309        }
310        return 0;
311    }
312   
313    int lineBisects(osg::Vec3Array *points, const unsigned int ip1, const osg::Vec2 p2) const
314    {
315        // return true if line starts at vertex <ip1> and lies between the 2 edges which meet at vertex
316        // <vertex> is that which uses index ip1.
317        // line is <vertex> to p2
318        //    return value is 0 - no crossing; 1,2,3 - which edge of the triangle is cut.
319        if (a_==ip1)
320        {
321            // first vertex is the vertex - test that a_ to p2 lies beteen edges a,b and a,c
322            osg::Vec3 apt=(*points)[a_];
323            osg::Vec3 bpt=(*points)[b_];
324            osg::Vec3 cpt=(*points)[c_];
325            return lineBisectTest(apt,bpt,cpt,p2)?1:0;
326        }
327        else if (b_==ip1)
328        {
329            // second vertex is the vertex - test that b_ to p2 lies beteen edges a,b and a,c
330            osg::Vec3 apt=(*points)[b_];
331            osg::Vec3 bpt=(*points)[c_];
332            osg::Vec3 cpt=(*points)[a_];
333            return lineBisectTest(apt,bpt,cpt,p2)?2:0;
334        }
335        else if (c_==ip1)
336        {
337            // 3rd vertex is the vertex - test that c_ to p2 lies beteen edges a,b and a,c
338            osg::Vec3 apt=(*points)[c_];
339            osg::Vec3 bpt=(*points)[a_];
340            osg::Vec3 cpt=(*points)[b_];
341            return lineBisectTest(apt,bpt,cpt,p2)?3:0;
342        }
343        return 0;
344    }
345   
346private:
347
348
349    bool intersect(const osg::Vec2 p1,const osg::Vec2 p2,const osg::Vec2 p3,const osg::Vec2 p4) const
350    {
351        // intersection point of p1,p2 and p3,p4
352        // test from http://astronomy.swin.edu.au/~pbourke/geometry/lineline2d/
353        // the intersection must be internal to the lines, not an end point.
354        float det=((p4.y()-p3.y())*(p2.x()-p1.x())-(p4.x()-p3.x())*(p2.y()-p1.y()));
355        if (det!=0)
356        {
357            // point on line is P=p1+ua.(p2-p1) and Q=p3+ub.(p4-p3)
358            float ua=((p4.x()-p3.x())*(p1.y()-p3.y())-(p4.y()-p3.y())*(p1.x()-p3.x()))/det;
359            float ub=((p2.x()-p1.x())*(p1.y()-p3.y())-(p2.y()-p1.y())*(p1.x()-p3.x()))/det;
360            if (ua> 0.00 && ua< 1 && ub> 0.0000  && ub< 1)
361            {
362                return true;
363            }
364        }
365        return false;
366    }
367   
368    Vertex_index a_;
369    Vertex_index b_;
370    Vertex_index c_;
371    osg::Vec3 cc_;   
372    Edge edge_[3];
373};
374
375typedef std::list<Triangle> Triangle_list;
376
377// comparison function for sorting sample points by the X coordinate
378bool Sample_point_compare(const osg::Vec3 &p1, const osg::Vec3 &p2)
379{
380    // replace pure sort by X coordinate with X then Y.
381    // errors can occur if the delaunay triangulation specifies 2 points at same XY and different Z
382    if (p1.x() != p2.x()) return p1.x() < p2.x();
383    if (p1.y() != p2.y()) return p1.y() < p2.y(); // GWM 30.06.05 - further rule if x coords are same.
384    OSG_INFO << "Two points are coincident at "<<p1.x() <<","<<p1.y() << std::endl;
385    return p1.z() < p2.z(); // never get here unless 2 points coincide
386}
387
388
389// container types
390typedef std::set<Edge, Edge::Less> Edge_set;
391
392
393DelaunayTriangulator::DelaunayTriangulator():
394    osg::Referenced()
395{
396}
397
398DelaunayTriangulator::DelaunayTriangulator(osg::Vec3Array *points, osg::Vec3Array *normals):
399    osg::Referenced(),
400    points_(points),
401    normals_(normals)
402{
403}
404
405DelaunayTriangulator::DelaunayTriangulator(const DelaunayTriangulator &copy, const osg::CopyOp &copyop):
406    osg::Referenced(copy),
407    points_(static_cast<osg::Vec3Array *>(copyop(copy.points_.get()))),
408    normals_(static_cast<osg::Vec3Array *>(copyop(copy.normals_.get()))),
409    prim_tris_(static_cast<osg::DrawElementsUInt *>(copyop(copy.prim_tris_.get())))
410{
411}
412
413DelaunayTriangulator::~DelaunayTriangulator()
414{
415}
416
417const Triangle * getTriangleWithEdge(const unsigned int ip1,const unsigned int ip2, const Triangle_list *triangles)
418{ // find triangle in list with edge from ip1 to ip2...
419    Triangle_list::const_iterator trconnitr; // connecting triangle
420    int idx=0;
421    for (trconnitr=triangles->begin(); trconnitr!=triangles->end(); )
422    {
423        if (trconnitr->isedge (ip1,ip2))
424        {
425            // this is the triangle.
426            return &(*trconnitr);
427        }
428        ++trconnitr;
429        idx++;
430    }
431    return NULL; //-1;
432}
433
434int DelaunayTriangulator::getindex(const osg::Vec3 &pt,const osg::Vec3Array *points)
435{
436    // return index of pt in points (or -1)
437    for (unsigned int i=0; i<points->size(); i++)
438    {
439        if (pt.x()==(*points)[i].x() &&pt.y()==(*points)[i].y() )
440        {
441            return i;
442        }
443    }
444    return -1;
445}
446
447Triangle_list fillHole(osg::Vec3Array *points,    std::vector<unsigned int> vindexlist)
448{
449    // eg clockwise vertex neighbours around the hole made by the constraint
450    Triangle_list triangles; // returned list
451    osg::ref_ptr<osg::Geometry> gtess=new osg::Geometry; // add all the contours to this for analysis
452    osg::ref_ptr<osg::Vec3Array> constraintverts=new osg::Vec3Array;
453    osg::ref_ptr<osgUtil::Tessellator> tscx=new osgUtil::Tessellator; // this assembles all the constraints
454   
455    for (std::vector<unsigned int>::iterator itint=vindexlist.begin(); itint!=vindexlist.end(); itint++)
456    {
457    //    OSG_WARN<< "add point " << (*itint) << " at " << (*points)[*itint].x() << ","<< (*points)[*itint].y() <<std::endl;
458        constraintverts->push_back((*points)[*itint]);
459    }
460   
461    unsigned int npts=vindexlist.size();
462
463    gtess->setVertexArray(constraintverts.get());
464    gtess->addPrimitiveSet(new osg::DrawArrays(osg::PrimitiveSet::POLYGON,0,npts));
465    tscx->setTessellationNormal(osg::Vec3(0.0,0.0,1.0));
466    tscx->setTessellationType(osgUtil::Tessellator::TESS_TYPE_GEOMETRY);
467    tscx->setBoundaryOnly(false);
468    tscx->setWindingType( osgUtil::Tessellator::TESS_WINDING_ODD); // the commonest tessellation is default, ODD. GE2 allows intersections of constraints to be found.
469    tscx->retessellatePolygons(*(gtess.get())); // this should insert extra vertices where constraints overlap
470
471    // extract triangles from gtess
472   
473    unsigned int ipr;
474    for (ipr=0; ipr<gtess->getNumPrimitiveSets(); ipr++)
475    {
476        unsigned int ic;
477        osg::PrimitiveSet* prset=gtess->getPrimitiveSet(ipr);
478        //                    OSG_WARN<< "gtess set " << ipr << " nprims " << prset->getNumPrimitives() <<
479        //                        " type " << prset->getMode() << std::endl;
480        unsigned int pidx,pidx1,pidx2;
481        switch (prset->getMode()) {
482        case osg::PrimitiveSet::TRIANGLES:
483            for (ic=0; ic<prset->getNumIndices()-2; ic+=3)
484            {
485                if (prset->index(ic)>=npts)
486                {
487                    // this is an added point.
488                    points->push_back((*constraintverts)[prset->index(ic)]);
489                    pidx=points->size()-1;
490                }
491                else
492                {
493                    pidx=vindexlist[prset->index(ic)];
494                }
495               
496                if (prset->index(ic+1)>=npts)
497                {
498                    // this is an added point.
499                    points->push_back((*constraintverts)[prset->index(ic+1)]);
500                    pidx1=points->size()-1;
501                }
502                else
503                {
504                    pidx1=vindexlist[prset->index(ic+1)];
505                }
506               
507                if (prset->index(ic+2)>=npts)
508                {
509                    // this is an added point.
510                    points->push_back((*constraintverts)[prset->index(ic+2)]);
511                    pidx2=points->size()-1;
512                }
513                else
514                {
515                    pidx2=vindexlist[prset->index(ic+2)];
516                }
517                triangles.push_back(Triangle(pidx, pidx1, pidx2, points));
518                //                    OSG_WARN<< "vert " << prset->index(ic) << " in array"<<std::endl;
519            }
520            break;
521        case osg::PrimitiveSet::TRIANGLE_STRIP: // 123, 234, 345...
522
523            for (ic=0; ic<prset->getNumIndices()-2; ic++)
524            {
525                if (prset->index(ic)>=npts)
526                {
527                    // this is an added point.
528                    points->push_back((*constraintverts)[prset->index(ic)]);
529                    pidx=points->size()-1;
530                } else {
531                    pidx=vindexlist[prset->index(ic)];
532                }
533                if (prset->index(ic+1)>=npts)
534                {
535                    // this is an added point.
536                    points->push_back((*constraintverts)[prset->index(ic+1)]);
537                    pidx1=points->size()-1;
538                }
539                else
540                {
541                    pidx1=vindexlist[prset->index(ic+1)];
542                }
543               
544                if (prset->index(ic+2)>=npts)
545                {
546                    // this is an added point.
547                    points->push_back((*constraintverts)[prset->index(ic+2)]);
548                    pidx2=points->size()-1;
549                }
550                else 
551                {
552                    pidx2=vindexlist[prset->index(ic+2)];
553                }
554               
555                if (ic%2==0)
556                {
557                    triangles.push_back(Triangle(pidx, pidx1, pidx2, points));
558                }
559                else
560                {
561                    triangles.push_back(Triangle(pidx1, pidx, pidx2, points));
562                }
563                //                    OSG_WARN<< "vert " << prset->index(ic) << " in array"<<std::endl;
564            }
565            break;
566           
567        case osg::PrimitiveSet::TRIANGLE_FAN:
568            {
569                if (prset->index(0)>=npts)
570                {
571                    // this is an added point.
572                    points->push_back((*constraintverts)[prset->index(0)]);
573                    pidx=points->size()-1;
574                }
575                else
576                {
577                    pidx=vindexlist[prset->index(0)];
578                }
579                //        OSG_WARN<< "tfan has " << prset->getNumIndices() << " indices"<<std::endl;
580                for (ic=1; ic<prset->getNumIndices()-1; ic++)
581                {
582                    if (prset->index(ic)>=npts)
583                    {
584                        // this is an added point.
585                        points->push_back((*constraintverts)[prset->index(ic)]);
586                        pidx1=points->size()-1;
587                    }
588                    else
589                    {
590                        pidx1=vindexlist[prset->index(ic)];
591                    }
592                   
593                    if (prset->index(ic+1)>=npts)
594                    { // this is an added point.
595                        points->push_back((*constraintverts)[prset->index(ic+1)]);
596                        pidx2=points->size()-1;
597                    }
598                    else
599                    {
600                        pidx2=vindexlist[prset->index(ic+1)];
601                    }
602                    triangles.push_back(Triangle(pidx, pidx1, pidx2, points));
603                }
604            }
605            break;
606        default:
607            OSG_WARN<< "WARNING set " << ipr << " nprims " << prset->getNumPrimitives() <<
608                " type " << prset->getMode() << " Type not triangle, tfan or strip"<< std::endl;
609            break;
610        }
611    }
612    return triangles;
613}
614
615template <typename TVector>
616void removeIndices( TVector& elements, unsigned int index )
617{
618    typename TVector::iterator itr = elements.begin();
619    while ( itr != elements.end() )
620    {
621        if ( (*itr)==index )
622        { // remove entirely
623            itr = elements.erase(itr);
624        }
625        else
626        {
627            if ((*itr)>index) --(*itr); // move indices down 1
628            ++itr; // next index
629        }
630    }
631 }
632
633void DelaunayConstraint::removeVerticesInside(const DelaunayConstraint *dco)
634{    /** remove vertices from this which are internal to dco.
635     * retains potins that are extremely close to edge of dco
636      * defined as edge of dco subtends>acs(0.999999)
637    */
638    int nrem=0;
639    osg::Vec3Array *vertices= dynamic_cast< osg::Vec3Array*>(getVertexArray());
640    if (vertices)
641    {
642        for (osg::Vec3Array::iterator vitr=vertices->begin(); vitr!=vertices->end(); )
643        {
644            if (dco->contains(*vitr))
645            {
646                unsigned int idx=vitr-vertices->begin(); // index of vertex
647                // remove vertex index from all the primitives
648                for (unsigned int ipr=0; ipr<getNumPrimitiveSets(); ipr++)
649                {
650                    osg::PrimitiveSet* prset=getPrimitiveSet(ipr);
651                    switch (prset->getType())
652                    {
653                    case osg::PrimitiveSet::DrawElementsUBytePrimitiveType:
654                        removeIndices( *static_cast<osg::DrawElementsUByte *>(prset), idx );
655                        break;
656                    case osg::PrimitiveSet::DrawElementsUShortPrimitiveType:
657                        removeIndices( *static_cast<osg::DrawElementsUShort *>(prset), idx );
658                        break;
659                    case osg::PrimitiveSet::DrawElementsUIntPrimitiveType:
660                        removeIndices( *static_cast<osg::DrawElementsUInt *>(prset), idx );
661                        break;
662                    default:
663                        OSG_WARN << "Invalid prset " <<ipr<< " tp " << prset->getType() << " types PrimitiveType,DrawArraysPrimitiveType=1 etc" << std::endl;
664                        break;
665                    }
666                }
667                vitr=vertices->erase(vitr);
668                nrem++;
669
670            }
671            else
672            {
673                vitr++;
674            }
675        }
676    }
677}
678
679void DelaunayConstraint::merge(DelaunayConstraint *dco)
680{
681    unsigned int ipr;
682    if (dco) { // 16 Dec 2006 just in case you pass in a NULL pointer
683        osg::Vec3Array* vmerge=dynamic_cast<osg::Vec3Array*>(getVertexArray());
684        if (!vmerge) vmerge=new osg::Vec3Array;
685        setVertexArray(vmerge);
686        for ( ipr=0; ipr<dco->getNumPrimitiveSets(); ipr++)
687        {
688            osg::PrimitiveSet* prset=dco->getPrimitiveSet(ipr);
689            osg::DrawArrays *drarr=dynamic_cast<osg::DrawArrays *> (prset);
690            if (drarr)
691            {
692                // need to add the offset of vmerge->size to each prset indices.
693                unsigned int noff=vmerge->size();
694                unsigned int n1=drarr->getFirst(); // usually 0
695                unsigned int numv=drarr->getCount(); //
696                addPrimitiveSet(new osg::DrawArrays(osg::PrimitiveSet::LINE_LOOP,n1+noff,numv));
697            }
698        }
699        osg::Vec3Array* varr=dynamic_cast<osg::Vec3Array*>(dco->getVertexArray());
700        if (varr) vmerge->insert(vmerge->end(),varr->begin(),varr->end());
701    }
702}
703
704void DelaunayTriangulator::_uniqueifyPoints()
705{
706    std::sort( points_->begin(), points_->end() );
707
708    osg::ref_ptr<osg::Vec3Array> temppts = new osg::Vec3Array;
709    // This won't work... must write our own unique() that compares only the first
710    // two terms of a Vec3 for equivalency
711    //std::insert_iterator< osg::Vec3Array > ti( *(temppts.get()), temppts->begin() );
712    //std::unique_copy( points_->begin(), points_->end(), ti );
713
714    osg::Vec3Array::iterator p = points_->begin();
715    osg::Vec3 v = *p;
716    // Always push back the first point
717    temppts->push_back( (v = *p));
718    for( ; p != points_->end(); p++ )
719    {
720        if( v[0] == (*p)[0] && v[1] == (*p)[1] )
721            continue;
722
723        temppts->push_back( (v = *p));
724    }
725
726    points_->clear();
727    std::insert_iterator< osg::Vec3Array > ci(*(points_.get()),points_->begin());
728    std::copy( temppts->begin(), temppts->end(), ci );
729}
730
731osgUtil::DelaunayConstraint *getconvexhull(osg::Vec3Array *points)
732{ // fits the 'rubberband' around the 2D points for uses as a delaunay constraint.
733    osg::ref_ptr<osgUtil::DelaunayConstraint> dcconvexhull=new osgUtil::DelaunayConstraint; // make
734    // convex hull around all the points
735    // start from first point (at minx); proceed to last x and back
736    osg::Vec3Array *verts=new osg::Vec3Array; // the hull points
737    verts->push_back(*(points->begin()) ); // min x/y point is guaranteed to be on the hull
738    verts->push_back(*(points->begin()+1) ); // second low x/y point is first length to be tested
739    for (osg::Vec3Array::iterator vit=(points->begin()+2); vit!=points->end(); vit++) {
740        // check if point lies outside the current last line segment
741        bool ok=1;
742        while (ok && verts->size()>1) {
743            osg::Vec3 lastseg=*(verts->end()-2)-*(verts->end()-1);
744            osg::Vec3 thisseg=(*vit)-*(verts->end()-1);
745            float cosang=(lastseg^thisseg).z();
746            if (cosang <0.0) { // pop off last point - *vit is further out hull
747                verts->pop_back();
748            } else { ok=0;}
749        }
750        verts->push_back(*vit ); // next low x/y point is next length to be tested
751        // check if the previous external angle is >180 - then remove previous point
752    }
753    for (osg::Vec3Array::reverse_iterator rvit=points->rbegin()+1; rvit!=points->rend(); rvit++) {
754        // check if point lies outside the current last line segment
755        bool ok=1;
756        while (ok && verts->size()>1) {
757            osg::Vec3 lastseg=*(verts->end()-2)-*(verts->end()-1);
758            osg::Vec3 thisseg=(*rvit)-*(verts->end()-1);
759            float cosang=(lastseg^thisseg).z();
760            if (cosang <0.0) { // pop off last point - *rvit is further out hull
761                verts->pop_back();
762            } else { ok=0;}
763        }
764        if ((*rvit)!=*(verts->begin())) verts->push_back(*rvit ); // next low x/y point is next length to be tested
765        // check if the previous external angle is >180 - then remove previous point
766    }
767    dcconvexhull->setVertexArray(verts);
768    dcconvexhull->addPrimitiveSet(new osg::DrawArrays(osg::PrimitiveSet::LINE_LOOP,0,verts->size()) );
769    return dcconvexhull.release();
770}
771
772bool DelaunayTriangulator::triangulate()
773{
774    // check validity of input array
775    if (!points_.valid())
776    {
777        OSG_WARN << "Warning: DelaunayTriangulator::triangulate(): invalid sample point array" << std::endl;
778        return false;
779    }
780
781    osg::Vec3Array *points = points_.get();
782
783    if (points->size() < 1)
784    {
785        OSG_WARN << "Warning: DelaunayTriangulator::triangulate(): too few sample points" << std::endl;
786        return false;
787    }
788
789    // Eliminate duplicate lat/lon points from input coordinates.
790    _uniqueifyPoints();
791
792
793    // initialize storage structures
794    Triangle_list triangles;
795    Triangle_list discarded_tris;   
796
797    // GWM July 2005 add constraint vertices to terrain
798    linelist::iterator linitr;
799    for (linitr=constraint_lines.begin();linitr!=constraint_lines.end();linitr++)
800    {
801        DelaunayConstraint* dc=(*linitr).get();
802        const osg::Vec3Array* vercon= dynamic_cast<const osg::Vec3Array*>(dc->getVertexArray());
803        if (vercon)
804        {
805            int nadded=0;
806            for (unsigned int icon=0;icon<vercon->size();icon++)
807            {
808                osg::Vec3 p1=(*vercon)[icon];
809                int idx=getindex(p1,points_.get());
810                if (idx<0)
811                { // only unique vertices are permitted.
812                    points_->push_back(p1); // add non-unique constraint points to triangulation
813                    nadded++;
814                }
815                else
816                {
817                    OSG_WARN << "DelaunayTriangulator: ignore a duplicate point at "<< p1.x()<< " " << p1.y() << std::endl;;
818                }
819            }
820        }
821    //    OSG_WARN<< "constraint size "<<vercon->size()<<" " <<nadded<< std::endl;
822    }
823        // GWM July 2005 end
824
825    // pre-sort sample points
826    OSG_INFO << "DelaunayTriangulator: pre-sorting sample points\n";
827    std::sort(points->begin(), points->end(), Sample_point_compare);   
828    // 24.12.06 add convex hull of points to force sensible outline.
829    osg::ref_ptr<osgUtil::DelaunayConstraint> dcconvexhull=getconvexhull(points);
830    addInputConstraint(dcconvexhull.get());
831
832    // set the last valid index for the point list
833    GLuint last_valid_index = points->size() - 1;   
834
835    // find the minimum and maximum x values in the point list
836    float minx = (*points)[0].x();
837    float maxx = (*points)[last_valid_index].x();
838
839    // find the minimum and maximum y values in the point list   
840    float miny = (*points)[0].y();
841    float maxy = miny;
842   
843    OSG_INFO << "DelaunayTriangulator: finding minimum and maximum Y values\n";
844    osg::Vec3Array::const_iterator mmi;
845    for (mmi=points->begin(); mmi!=points->end(); ++mmi)
846    {
847        if (mmi->y() < miny) miny = mmi->y();
848        if (mmi->y() > maxy) maxy = mmi->y();
849    }
850   
851    // add supertriangle vertices to the point list
852    // gwm added 1.05* to ensure that supervertices are outside the domain of points.
853    // original value could make 2 coincident points for regular arrays of x,y,h data.
854    // this mod allows regular spaced arrays to be used.
855    // 16 Dec 2006 this increase in size encourages the supervertex triangles to be long and thin
856    // thus ensuring that the convex hull of the terrain points are edges in the delaunay triangulation
857    // the values do however result in a small loss of numerical resolution.
858    points_->push_back(osg::Vec3(minx - .10*(maxx - minx), miny - .10*(maxy - miny), 0));
859    points_->push_back(osg::Vec3(maxx + .10*(maxx - minx), miny - .10*(maxy - miny), 0));
860    points_->push_back(osg::Vec3(maxx + .10*(maxx - minx), maxy + .10*(maxy - miny), 0));
861    points_->push_back(osg::Vec3(minx - .10*(maxx - minx), maxy + .10*(maxy - miny), 0));
862                                                                   
863    // add supertriangles to triangle list                           
864    triangles.push_back(Triangle(last_valid_index+1, last_valid_index+2, last_valid_index+3, points));
865    triangles.push_back(Triangle(last_valid_index+4, last_valid_index+1, last_valid_index+3, points));
866
867   
868    // begin triangulation   
869    GLuint pidx = 0;
870    osg::Vec3Array::const_iterator i;   
871   
872    OSG_INFO << "DelaunayTriangulator: triangulating vertex grid (" << (points->size()-3) <<" points)\n";   
873
874    for (i=points->begin(); i!=points->end(); ++i, ++pidx)
875    {
876
877        // don't process supertriangle vertices
878        if (pidx > last_valid_index) break;
879
880        Edge_set edges;
881
882        // iterate through triangles
883        Triangle_list::iterator j, next_j;
884        for (j=triangles.begin(); j!=triangles.end(); j = next_j)
885        {
886
887            next_j = j;
888            ++next_j;
889
890            // get the circumcircle (x,y centre & radius)
891            osg::Vec3 cc = j->get_circumcircle();
892
893            // OPTIMIZATION: since points are pre-sorted by the X component,
894            // check whether we can discard this triangle for future operations
895            float xdist = i->x() - cc.x();
896            // this is where the circumcircles radius rather than R^2 is faster.
897            // original code used r^2 and needed to test xdist*xdist>cc.z && i->x()>cc.x().
898            if ((xdist ) > cc.z() )
899            {
900                discarded_tris.push_back(*j); // these are not needed for further tests as no more
901                // points will ever lie inside this triangle.
902                triangles.erase(j);
903            }
904            else
905            {
906
907                // if the point lies in the triangle's circumcircle then add
908                // its edges to the edge list and remove the triangle
909                if (point_in_circle(*i, cc))
910                {
911                    for (int ei=0; ei<3; ++ei)
912                    {
913                        std::pair<Edge_set::iterator, bool> result = edges.insert(j->get_edge(ei));
914                        if (!result.second)
915                        {
916                            // cast away constness of a set element, which is
917                            // safe in this case since the set_duplicate is
918                            // not used as part of the Less operator.
919                            Edge& edge = const_cast<Edge&>(*(result.first));
920                            // not clear why this change is needed? But prevents removal of twice referenced edges??
921                      //      edge.set_duplicate(true);
922                            edge.set_duplicate(!edge.get_duplicate());
923                        }
924                    }                   
925                    triangles.erase(j);
926                }
927            }
928        }
929
930        // remove duplicate edges and add new triangles
931        Edge_set::iterator ci;
932        for (ci=edges.begin(); ci!=edges.end(); ++ci)
933        {
934            if (!ci->get_duplicate())
935            {
936                triangles.push_back(Triangle(pidx, ci->ib(), ci->ie(), points));
937            }
938        }
939    }
940    // dec 2006 we used to remove supertriangle vertices here, but then we cant strictly use the supertriangle
941    // vertices to find intersections of constraints with terrain, so moved to later.
942
943    OSG_INFO << "DelaunayTriangulator: finalizing and cleaning up structures\n";
944
945     // rejoin the two triangle lists
946    triangles.insert(triangles.begin(), discarded_tris.begin(), discarded_tris.end());
947
948        // GWM July 2005 eliminate any triangle with an edge crossing a constraint line
949    // http://www.geom.uiuc.edu/~samuelp/del_project.html
950    // we could also implement the sourcecode in http://gts.sourceforge.net/reference/gts-delaunay-and-constrained-delaunay-triangulations.html
951    // this uses the set of lines which are boundaries of the constraints, including points
952    // added to the contours by tessellation.
953    for (linelist::iterator dcitr=constraint_lines.begin();dcitr!=constraint_lines.end();dcitr++)
954    {
955        //DelaunayConstraint *dc=(*dcitr).get();
956        const osg::Vec3Array* vercon = dynamic_cast<const osg::Vec3Array*>((*dcitr)->getVertexArray());
957        if (vercon)
958        {
959            for (unsigned int ipr=0; ipr<(*dcitr)->getNumPrimitiveSets(); ipr++)
960            {
961                const osg::PrimitiveSet* prset=(*dcitr)->getPrimitiveSet(ipr);
962                if (prset->getMode()==osg::PrimitiveSet::LINE_LOOP ||
963                    prset->getMode()==osg::PrimitiveSet::LINE_STRIP)
964                {
965                    // loops or strips
966                    // start with the last point on the loop
967                    unsigned int ip1=getindex((*vercon)[prset->index (prset->getNumIndices()-1)],points_.get());
968                    for (unsigned int i=0; i<prset->getNumIndices(); i++)
969                    {
970                        unsigned int ip2=getindex((*vercon)[prset->index(i)],points_.get());
971                        if (i>0 || prset->getMode()==osg::PrimitiveSet::LINE_LOOP)
972                        {
973                            // dont check edge from end to start
974                            // for strips
975                            // 2 points on the constraint
976                            bool edgused=false;// first check for exact edge indices are used.
977                            Triangle_list::iterator titr;
978                            int it=0;
979                            for (titr=triangles.begin(); titr!=triangles.end() && !edgused; ++titr)
980                            {
981                                //check that the edge ip1-ip2 is not already part of the triangulation.
982                                if (titr->isedge(ip1,ip2)) edgused=true;
983                                if (titr->isedge(ip2,ip1)) edgused=true;
984                                //        if (edgused) OSG_WARN << "Edge used in triangle " << it << " " <<
985                                //            titr->a()<<","<< titr->b()<<","<< titr->c()<<  std::endl;
986                                it++;
987                            }
988                            if (!edgused)
989                            {
990                                // then check for intermediate triangles, erase them and replace with constrained triangles.
991                                // find triangle with point ip1 where the 2 edges from ip1 contain the line p1-p2.
992                                osg::Vec2 p1((*points_)[ip1].x(),(*points_)[ip1].y()); // a constraint line joins p1-p2
993                                osg::Vec2 p2((*points_)[ip2].x(),(*points_)[ip2].y());
994                                int ntr=0;
995                                std::vector<const Triangle *> trisToDelete; // array of triangles to delete from terrain.
996                                // form 2 lists of vertices for the edges of the hole created.
997                                // The hole joins vertex ip1 to ip2, and one list of edges lies to the left
998                                // of the line ip1-ip2m the other to the right.
999                                // a list of vertices forming 2 halves of the removed triangles.
1000                                // which in turn are filled in with the tessellator.
1001                                for (titr=triangles.begin(); titr!=triangles.end(); )
1002                                {
1003                                    int icut=titr->lineBisects(points_.get(),ip1,p2);
1004                                    //    OSG_WARN << "Testing triangle " << ntr << " "<< ip1 << " ti " <<
1005                                    //        titr->a()<< ","<<titr->b() <<"," <<titr->c() << std::endl;
1006                                    if (icut>0)
1007                                    {
1008                                        // triangle titr starts the constraint edge
1009                                        std::vector<unsigned int> edgeRight, edgeLeft;
1010                                        edgeRight.push_back(ip1);
1011                                        edgeLeft.push_back(ip1);
1012                                        //        OSG_WARN << "hole first " << edgeLeft.back()<<  " rt " << edgeRight.back()<< std::endl;
1013                                        trisToDelete.push_back(&(*titr));
1014                                        // now find the unique triangle that shares the defined edge
1015                                        unsigned int e1, e2; // indices of ends of test triangle titr
1016                                        if    (icut==1)
1017                                        {
1018                                            // icut=1 implies vertex a is not involved
1019                                            e1=titr->b(); e2=titr->c();
1020                                        }
1021                                        else if (icut==2)
1022                                        {
1023                                            e1=titr->c(); e2=titr->a();
1024                                        }
1025                                        else if (icut==3)
1026                                        {
1027                                            e1=titr->a(); e2=titr->b();
1028                                        }
1029                                        edgeRight.push_back(e2);
1030                                        edgeLeft.push_back(e1);
1031                                        //        OSG_WARN << icut << "hole edges " << edgeLeft.back()<<  " rt " << edgeRight.back()<< std::endl;
1032                                        const Triangle *tradj=getTriangleWithEdge(e2,e1, &triangles);
1033                                        if (tradj)
1034                                        {
1035                                            while (tradj && !tradj->usesVertex(ip2) && trisToDelete.size()<999)
1036                                            {
1037                                                trisToDelete.push_back(tradj);
1038                                                icut=tradj->whichEdge(points_.get(),p1,p2,e1,e2);
1039                                                //    OSG_WARN  << ntr << " cur triedge " << icut << " " << ip1 <<
1040                                                //        " to " << ip2 << " tadj " << tradj->a()<< ","<<tradj->b() <<","
1041                                                //        <<tradj->c() <<std::endl;
1042                                                if        (icut==1) {e1=tradj->b(); e2=tradj->c();} // icut=1 implies vertex a is not involved
1043                                                else if (icut==2) {e1=tradj->c(); e2=tradj->a();}
1044                                                else if (icut==3) {e1=tradj->a(); e2=tradj->b();}
1045                                                if (edgeLeft.back()!=e1 && edgeRight.back()==e2 && e1!=ip2) {
1046                                                    edgeLeft.push_back(e1);
1047                                                } else if(edgeRight.back()!=e2 && edgeLeft.back()==e1 && e2!=ip2) {
1048                                                    edgeRight.push_back(e2);
1049                                                } else {
1050                                                    if (!tradj->usesVertex(ip2)) OSG_WARN << "tradj error " << tradj->a()<<  " , " << tradj->b()<<  " , " << tradj->c()<< std::endl;
1051                                                }
1052                                                const Triangle *previousTradj = tradj;
1053                                                tradj=getTriangleWithEdge(e2,e1, &triangles);
1054                                                if (tradj == previousTradj) {
1055                                                    tradj = 0;
1056                                                }
1057                                            }
1058                                            if (trisToDelete.size()>=900) {
1059                                                OSG_WARN << " found " << trisToDelete.size() << " adjacent tris " <<std::endl;
1060                                            }
1061                                        }
1062
1063                                        // both lines end at ip2 point.
1064                                        edgeLeft.push_back(ip2);
1065                                        edgeRight.push_back(ip2);
1066                                        if (tradj) trisToDelete.push_back(tradj);
1067                                        //        OSG_WARN << icut << "hole last " << edgeLeft.back()<<  " rt " << edgeRight.back()<< std::endl;
1068                                        Triangle_list constrainedtris=fillHole(points_.get(),edgeLeft);
1069                                        triangles.insert(triangles.begin(), constrainedtris.begin(), constrainedtris.end());
1070                                        constrainedtris=fillHole(points_.get(),edgeRight);
1071                                        triangles.insert(triangles.begin(), constrainedtris.begin(), constrainedtris.end());
1072
1073                                    }
1074                                    ++titr;
1075                                    ntr++;
1076                                }
1077                                // remove the triangles list
1078                                Triangle_list::iterator tri; // counts through triangles
1079                                for (tri=triangles.begin(); tri!=triangles.end(); )
1080                                {
1081                                    bool deleted=false;
1082                                    for (std::vector<const Triangle *>::iterator deleteTri=trisToDelete.begin();
1083                                    deleteTri!=trisToDelete.end(); )
1084                                    {
1085                                        if (&(*tri)==*deleteTri)
1086                                        {
1087                                            deleted=true;
1088                                            tri=triangles.erase(tri);
1089                                            deleteTri=trisToDelete.erase(deleteTri); // 24.12.06 remove from delete list.
1090                                        } else {deleteTri++; }
1091                                    }
1092                                    if (!deleted) ++tri;
1093                                }
1094                            }
1095                        } // strip test
1096
1097                        ip1=ip2; // next edge of line
1098                    }
1099                }
1100            }
1101        }
1102    }
1103    // GWM Sept 2005 end
1104    // dec 2006 remove supertriangle vertices - IF we have added some internal vertices (see fillholes)
1105    // then these may not be the last vertices in the list.
1106//    } else { // remove 3 super-triangle vertices more completely, moving any reference indices down.
1107    Triangle_list::iterator tri;
1108    GLuint supertriend = last_valid_index+4;
1109    for (tri=triangles.begin(); tri!=triangles.end();)
1110    { // look for triangles using the supertriangle indices or >super indices and move down by 3.
1111        if ((tri->a() > last_valid_index && tri->a() <= supertriend) ||
1112            (tri->b() > last_valid_index && tri->b() <= supertriend ) ||
1113            (tri->c() > last_valid_index && tri->c() <= supertriend )) {
1114            tri=triangles.erase(tri);
1115        } else { // move down by 3 tests
1116            if (tri->a() > last_valid_index) { // move index down 4
1117                tri->incrementa(-4);
1118            }
1119            if (tri->b() > last_valid_index) { // move down 4
1120                tri->incrementb(-4);
1121            }
1122            if (tri->c() > last_valid_index) { // move down 4 -- correction 21.12.06- was b() should test index c()
1123                tri->incrementc(-4);
1124            }
1125            ++tri; // only increment tri here as the other path increments tri when tri=triangles.erase.
1126        }
1127    }
1128        // remove 3 supertriangle vertices from points. They may not be the last vertices in points if
1129        // extra points have been inserted by the constraint re-triangulation.
1130    points->erase(points->begin()+last_valid_index+1,points->begin()+last_valid_index+5);
1131    //last_valid_index = points->size()-1; // the last valid vertex is last point.
1132    // end of dec 2006 changes.
1133
1134    // initialize index storage vector
1135    std::vector<GLuint> pt_indices;
1136    pt_indices.reserve(triangles.size() * 3);
1137
1138    // build osg primitive
1139    OSG_INFO << "DelaunayTriangulator: building primitive(s)\n";
1140    Triangle_list::const_iterator ti;
1141    for (ti=triangles.begin(); ti!=triangles.end(); ++ti)
1142    {
1143
1144        // don't add this triangle to the primitive if it shares any vertex with
1145        // the supertriangle triangles have already been removed.
1146        // Don't need this test: ti->a() <= last_valid_index && ti->b() <= last_valid_index && ti->c() <= last_valid_index &&
1147          // Don't add degenerate (zero radius) triangles
1148        if ( ti->get_circumcircle().z()>0.0)
1149        {
1150
1151            if (normals_.valid())
1152            {
1153                (normals_.get())->push_back(ti->compute_normal(points));
1154            }
1155
1156            pt_indices.push_back(ti->a());
1157            pt_indices.push_back(ti->b());
1158            pt_indices.push_back(ti->c());
1159        }
1160    }
1161
1162    prim_tris_ = new osg::DrawElementsUInt(GL_TRIANGLES, pt_indices.size(), &(pt_indices.front()));
1163
1164    OSG_INFO << "DelaunayTriangulator: process done, " << prim_tris_->getNumPrimitives() << " triangles remain\n";
1165   
1166    return true;
1167}
1168
1169void DelaunayTriangulator::removeInternalTriangles(DelaunayConstraint *dc )
1170{
1171    if (dc) { // 16.12.06 just in case....
1172        // Triangle_list *triangles
1173        // remove triangle from terrain prim_tris_ internal to each constraintline
1174        // and move to the constraint line to make an alternative geometry,
1175        // possibly with alternative texture, and texture map
1176        int ndel=0;
1177        osg::Vec3Array::iterator normitr;
1178        if( normals_.valid() )
1179            normitr = normals_->begin();
1180
1181        //        OSG_WARN << "DelaunayTriangulator: removeinternals, " << std::endl;
1182        for (osg::DrawElementsUInt::iterator triit=prim_tris_->begin(); triit!=prim_tris_->end(); )
1183        {
1184            // triangle joins points_[itr, itr+1, itr+2]
1185            Triangle tritest((*triit), *(triit+1), *(triit+2), points_.get());
1186            if ( dc->contains(tritest.compute_centroid( points_.get()) ) )
1187            {
1188                // centroid is inside the triangle, so IF inside linear, remove
1189                // OSG_WARN << "DelaunayTriangulator: remove, " << (*triit) << "," << *(triit+1) <<","<<*(triit+2)<< std::endl;
1190                dc->addtriangle((*triit), *(triit+1), *(triit+2));
1191                triit=prim_tris_->erase(triit);
1192                triit=prim_tris_->erase(triit);
1193                triit=prim_tris_->erase(triit);
1194                if (normals_.valid())
1195                {
1196                    // erase the corresponding normal
1197                    normitr=normals_->erase(normitr);
1198                }
1199                ndel++;
1200            }
1201            else
1202            {
1203                if (normals_.valid())
1204                {
1205                    normitr++;
1206                }
1207
1208                triit+=3;
1209            }
1210        }
1211
1212        OSG_INFO << "end of test dc, deleted " << ndel << std::endl;
1213    }
1214}
1215//=== DelaunayConstraint functions
1216
1217float DelaunayConstraint::windingNumber(const osg::Vec3 &testpoint) const
1218{
1219    // return winding number of loop around testpoint. Only in 2D, x-y coordinates assumed!
1220    float theta=0; // sum of angles subtended by the line array - the winding number
1221    const osg::Vec3Array *vertices= dynamic_cast<const osg::Vec3Array*>(getVertexArray());
1222    if (vertices)
1223    {
1224        for (unsigned int ipr=0; ipr<getNumPrimitiveSets(); ipr++)
1225        {
1226            const osg::PrimitiveSet* prset=getPrimitiveSet(ipr);
1227            if (prset->getMode()==osg::PrimitiveSet::LINE_LOOP)
1228            {
1229                // nothing else loops
1230                // start with the last point on the loop
1231                const osg::Vec3 prev=(*vertices)[prset->index (prset->getNumIndices()-1)];
1232                osg::Vec3 pi(prev.x()-testpoint.x(),prev.y()-testpoint.y(),0);
1233                pi.normalize();
1234                for (unsigned int i=0; i<prset->getNumIndices(); i++)
1235                {
1236                    const osg::Vec3 curp=(*vertices)[prset->index (i)];
1237                    osg::Vec3 edge(curp.x()-testpoint.x(),curp.y()-testpoint.y(),0);
1238                    edge.normalize();
1239                    double cth=edge*pi;
1240                    if (cth<=-0.99999 )
1241                    {
1242                        // testpoint is on edge and between 2 points
1243                        return 0; //
1244                    }
1245                    else
1246                    {
1247                        if (cth<0.99999)
1248                        {
1249                            float dang=(cth<1 && cth>-1)?acos(edge*pi):0; // this is unsigned angle
1250                            float zsign=edge.x()*pi.y()-pi.x()*edge.y(); // z component of..(edge^pi).z();
1251                            if (zsign>0) theta+=dang; // add the angle subtended appropriately
1252                            else if (zsign<0) theta-=dang;
1253                        }
1254                    }
1255                    pi=edge;
1256                }
1257            }
1258        }
1259    }
1260   
1261    return theta/osg::PI/2.0; // should be 0 or 2 pi.
1262}
1263osg::DrawElementsUInt *DelaunayConstraint::makeDrawable()
1264{
1265    // initialize index storage vector for internal triangles.
1266    std::vector<GLuint> pt_indices;
1267    pt_indices.reserve(_interiorTris.size() * 3);
1268    trilist::const_iterator ti;
1269    for (ti=_interiorTris.begin(); ti!=_interiorTris.end(); ++ti)
1270    {
1271       
1272        //  if (normals_.valid()) {
1273        //        (normals_.get())->push_back(ti->compute_normal(points));
1274        //  }
1275       
1276        pt_indices.push_back((*ti)[0]);
1277        pt_indices.push_back((*ti)[1]);
1278        pt_indices.push_back((*ti)[2]);
1279    }
1280    prim_tris_ = new osg::DrawElementsUInt(GL_TRIANGLES, pt_indices.size(), &(pt_indices.front()));
1281   
1282    return prim_tris_.get();
1283}
1284bool DelaunayConstraint::contains(const osg::Vec3 &testpoint) const 
1285{
1286    // true if point is internal to the loop.
1287    float theta=windingNumber(testpoint); // sum of angles subtended by the line array - the winding number
1288    return fabs(theta)>0.9; // should be 0 or 1 (or 2,3,4 for very complex not permitted loops).
1289}
1290bool DelaunayConstraint::outside(const osg::Vec3 &testpoint) const 
1291{
1292    // true if point is outside the loop.
1293    float theta=windingNumber(testpoint); // sum of angles subtended by the line array - the winding number
1294    return fabs(theta)<.05; // should be 0 if outside.
1295}
1296
1297
1298void DelaunayConstraint::addtriangle(int i1, int i2, int i3)
1299{
1300    // a triangle joins vertices i1,i2,i3 in the points of the delaunay triangles.
1301    // points is the array of poitns in the triangulator;
1302    // add triangle to the constraint
1303    int *ip=new int[3];
1304    ip[0]=i1;
1305    ip[1]=i2;
1306    ip[2]=i3;
1307    _interiorTris.push_back(ip);
1308}
1309osg::Vec3Array* DelaunayConstraint::getPoints(const osg::Vec3Array *points)
1310{
1311    //points_ is the array of points that can be used to render the triangles in this DC.
1312    osg::ref_ptr<osg::Vec3Array> points_=new osg::Vec3Array;
1313    trilist::iterator ti;
1314    for (ti=_interiorTris.begin(); ti!=_interiorTris.end(); ++ti) {
1315        int idx=0;
1316        int ip[3]={-1,-1,-1};
1317        // find if points[i1/i2/i3] already in the vertices points_
1318        for (osg::Vec3Array::iterator ivert=points_->begin(); ivert!=points_->end(); ivert++)
1319        {
1320            if (ip[0]<0 && *ivert==(*points)[(*ti)[0]])
1321            {
1322                (*ti)[0]=ip[0]=idx;
1323            }
1324            if (ip[1]<0 && *ivert==(*points)[(*ti)[1]])
1325            {
1326                (*ti)[1]=ip[1]=idx;
1327            }
1328            if (ip[2]<0 && *ivert==(*points)[(*ti)[2]])
1329            {
1330                (*ti)[2]=ip[2]=idx;
1331            }
1332            idx++;
1333        }
1334        if (ip[0]<0)
1335        {
1336            points_->push_back((*points)[(*ti)[0]]);
1337            (*ti)[0]=ip[0]=points_->size()-1;
1338        }
1339        if (ip[1]<0)
1340        {
1341            points_->push_back((*points)[(*ti)[1]]);
1342            (*ti)[1]=ip[1]=points_->size()-1;
1343        }
1344        if (ip[2]<0)
1345        {
1346            points_->push_back((*points)[(*ti)[2]]);
1347            (*ti)[2]=ip[2]=points_->size()-1;
1348        }
1349    }
1350    makeDrawable();
1351    return points_.release();
1352}
1353
1354void DelaunayConstraint::handleOverlaps(void)
1355{
1356    // use tessellator to interpolate crossing vertices.
1357    osg::ref_ptr<osgUtil::Tessellator> tscx=new osgUtil::Tessellator; // this assembles all the constraints
1358    tscx->setTessellationType(osgUtil::Tessellator::TESS_TYPE_GEOMETRY);
1359    tscx->setBoundaryOnly(true);
1360    tscx->setWindingType( osgUtil::Tessellator::TESS_WINDING_ODD);
1361    //  ODD chooses the winding =1, NOT overlapping areas of constraints.
1362    // nb this includes all the edges where delaunay constraints meet
1363    // draw a case to convince yourself!.
1364   
1365    tscx->retessellatePolygons(*this); // find all edges
1366}
1367
1368} // namespace osgutil
Note: See TracBrowser for help on using the browser.