Celestia

1
// universe.cpp
2
//
3
// Copyright (C) 2001-2009, the Celestia Development Team
4
// Original version by Chris Laurel <claurel@gmail.com>
5
//
6
// A container for catalogs of galaxies, stars, and planets.
7
//
8
// This program is free software; you can redistribute it and/or
9
// modify it under the terms of the GNU General Public License
10
// as published by the Free Software Foundation; either version 2
11
// of the License, or (at your option) any later version.
12

13
#include "universe.h"
14

15
#include <algorithm>
16
#include <cassert>
17
#include <cmath>
18
#include <utility>
19

20
#include <celcompat/numbers.h>
21
#include <celmath/mathlib.h>
22
#include <celmath/intersect.h>
23
#include <celmath/ray.h>
24
#include <celutil/greek.h>
25
#include <celutil/utf8.h>
26
#include "asterism.h"
27
#include "body.h"
28
#include "boundaries.h"
29
#include "frametree.h"
30
#include "location.h"
31
#include "meshmanager.h"
32
#include "render.h"
33
#include "timelinephase.h"
34

35
namespace engine = celestia::engine;
36
namespace math = celestia::math;
37
namespace util = celestia::util;
38

39
namespace
40
{
41

42
constexpr double ANGULAR_RES = 3.5e-6;
43

44
class ClosestStarFinder : public engine::StarHandler
45
{
46
public:
47
    ClosestStarFinder(float _maxDistance, const Universe* _universe);
48
    ~ClosestStarFinder() = default;
49
    void process(const Star& star, float distance, float appMag) override;
50

51
public:
52
    float maxDistance;
53
    float closestDistance;
54
    const Star* closestStar;
55
    const Universe* universe;
56
    bool withPlanets;
57
};
58

59
ClosestStarFinder::ClosestStarFinder(float _maxDistance,
60
                                     const Universe* _universe) :
61
    maxDistance(_maxDistance),
62
    closestDistance(_maxDistance),
63
    closestStar(nullptr),
64
    universe(_universe),
65
    withPlanets(false)
66
{
67
}
68

69
void
70
ClosestStarFinder::process(const Star& star, float distance, float /*unused*/)
71
{
72
    if (distance < closestDistance)
73
    {
74
        if (!withPlanets || universe->getSolarSystem(&star))
75
        {
76
            closestStar = &star;
77
            closestDistance = distance;
78
        }
79
    }
80
}
81

82
class NearStarFinder : public engine::StarHandler
83
{
84
public:
85
    NearStarFinder(float _maxDistance, std::vector<const Star*>& nearStars);
86
    ~NearStarFinder() = default;
87
    void process(const Star& star, float distance, float appMag);
88

89
private:
90
    float maxDistance;
91
    std::vector<const Star*>& nearStars;
92
};
93

94
NearStarFinder::NearStarFinder(float _maxDistance,
95
                               std::vector<const Star*>& _nearStars) :
96
    maxDistance(_maxDistance),
97
    nearStars(_nearStars)
98
{
99
}
100

101
void
102
NearStarFinder::process(const Star& star, float distance, float /*unused*/)
103
{
104
    if (distance < maxDistance)
105
        nearStars.push_back(&star);
106
}
107

108
struct PlanetPickInfo
109
{
110
    double sinAngle2Closest;
111
    double closestDistance;
112
    double closestApproxDistance;
113
    Body* closestBody;
114
    Eigen::ParametrizedLine<double, 3> pickRay;
115
    double jd;
116
    float atanTolerance;
117
};
118

119
bool
120
ApproxPlanetPickTraversal(Body* body, PlanetPickInfo& pickInfo)
121
{
122
    // Reject invisible bodies and bodies that don't exist at the current time
123
    if (!body->isVisible() || !body->extant(pickInfo.jd) || !body->isClickable())
124
        return true;
125

126
    Eigen::Vector3d bpos = body->getAstrocentricPosition(pickInfo.jd);
127
    Eigen::Vector3d bodyDir = bpos - pickInfo.pickRay.origin();
128
    double distance = bodyDir.norm();
129

130
    // Check the apparent radius of the orbit against our tolerance factor.
131
    // This check exists to make sure than when picking a distant, we select
132
    // the planet rather than one of its satellites.
133
    if (auto appOrbitRadius = static_cast<float>(body->getOrbit(pickInfo.jd)->getBoundingRadius() / distance);
134
        std::max(static_cast<double>(pickInfo.atanTolerance), ANGULAR_RES) > appOrbitRadius)
135
    {
136
        return true;
137
    }
138

139
    bodyDir.normalize();
140
    Eigen::Vector3d bodyMiss = bodyDir - pickInfo.pickRay.direction();
141
    if (double sinAngle2 = bodyMiss.norm() / 2.0; sinAngle2 <= pickInfo.sinAngle2Closest)
142
    {
143
        pickInfo.sinAngle2Closest = std::max(sinAngle2, ANGULAR_RES);
144
        pickInfo.closestBody = body;
145
        pickInfo.closestApproxDistance = distance;
146
    }
147

148
    return true;
149
}
150

151
// Perform an intersection test between the pick ray and a body
152
bool
153
ExactPlanetPickTraversal(Body* body, PlanetPickInfo& pickInfo)
154
{
155
    Eigen::Vector3d bpos = body->getAstrocentricPosition(pickInfo.jd);
156
    float radius = body->getRadius();
157
    double distance = -1.0;
158

159
    // Test for intersection with the bounding sphere
160
    if (!body->isVisible() || !body->extant(pickInfo.jd) || !body->isClickable() ||
161
        !math::testIntersection(pickInfo.pickRay, math::Sphered(bpos, radius), distance))
162
        return true;
163

164
    if (body->getGeometry() == InvalidResource)
165
    {
166
        // There's no mesh, so the object is an ellipsoid.  If it's
167
        // spherical, we've already done all the work we need to. Otherwise,
168
        // we need to perform a ray-ellipsoid intersection test.
169
        if (!body->isSphere())
170
        {
171
            Eigen::Vector3d ellipsoidAxes = body->getSemiAxes().cast<double>();
172

173
            // Transform rotate the pick ray into object coordinates
174
            Eigen::Matrix3d m = body->getEclipticToEquatorial(pickInfo.jd).toRotationMatrix();
175
            Eigen::ParametrizedLine<double, 3> r(pickInfo.pickRay.origin() - bpos, pickInfo.pickRay.direction());
176
            r = math::transformRay(r, m);
177
            if (!math::testIntersection(r, math::Ellipsoidd(ellipsoidAxes), distance))
178
                distance = -1.0;
179
        }
180
    }
181
    else
182
    {
183
        // Transform rotate the pick ray into object coordinates
184
        Eigen::Quaterniond qd = body->getGeometryOrientation().cast<double>();
185
        Eigen::Matrix3d m = (qd * body->getEclipticToBodyFixed(pickInfo.jd)).toRotationMatrix();
186
        Eigen::ParametrizedLine<double, 3> r(pickInfo.pickRay.origin() - bpos, pickInfo.pickRay.direction());
187
        r = math::transformRay(r, m);
188

189
        const Geometry* geometry = engine::GetGeometryManager()->find(body->getGeometry());
190
        float scaleFactor = body->getGeometryScale();
191
        if (geometry != nullptr && geometry->isNormalized())
192
            scaleFactor = radius;
193

194
        // The mesh vertices are normalized, then multiplied by a scale
195
        // factor.  Thus, the ray needs to be multiplied by the inverse of
196
        // the mesh scale factor.
197
        double is = 1.0 / scaleFactor;
198
        r.origin() *= is;
199
        r.direction() *= is;
200

201
        if (geometry != nullptr && !geometry->pick(r, distance))
202
            distance = -1.0;
203
    }
204
    // Make also sure that the pickRay does not intersect the body in the
205
    // opposite hemisphere! Hence, need again the "bodyMiss" angle
206

207
    Eigen::Vector3d bodyDir = bpos - pickInfo.pickRay.origin();
208
    bodyDir.normalize();
209
    Eigen::Vector3d bodyMiss = bodyDir - pickInfo.pickRay.direction();
210

211
    if (double sinAngle2 = bodyMiss.norm() / 2.0;
212
        sinAngle2 < (celestia::numbers::sqrt2 * 0.5) && // sin(45 degrees) = sqrt(2)/2
213
        distance > 0.0 && distance <= pickInfo.closestDistance)
214
    {
215
        pickInfo.closestDistance = distance;
216
        pickInfo.closestBody = body;
217
    }
218

219
    return true;
220
}
221

222
// Recursively traverse a frame tree; call the specified callback function for each
223
// body in the tree. The callback function returns a boolean indicating whether
224
// traversal should continue.
225
//
226
// TODO: This function works, but could use some cleanup:
227
//   * Make it a member of the frame tree class
228
//   * Combine info and func into a traversal callback class
229
template<typename F>
230
bool
231
traverseFrameTree(const FrameTree* frameTree,
232
                  double tdb,
233
                  F func,
234
                  PlanetPickInfo& info)
235
{
236
    for (unsigned int i = 0; i < frameTree->childCount(); i++)
237
    {
238
        const TimelinePhase* phase = frameTree->getChild(i);
239
        if (!phase->includes(tdb))
240
            continue;
241

242
        Body* body = phase->body();
243
        if (!func(body, info))
244
            return false;
245

246
        if (const FrameTree* bodyFrameTree = body->getFrameTree();
247
            bodyFrameTree != nullptr && !traverseFrameTree(bodyFrameTree, tdb, func, info))
248
        {
249
            return false;
250
        }
251
    }
252

253
    return true;
254
}
255

256
// StarPicker is a callback class for StarDatabase::findVisibleStars
257
class StarPicker : public engine::StarHandler
258
{
259
public:
260
    StarPicker(const Eigen::Vector3f&, const Eigen::Vector3f&, double, float);
261
    ~StarPicker() = default;
262

263
    void process(const Star& /*star*/, float /*unused*/, float /*unused*/) override;
264

265
public:
266
    const Star* pickedStar;
267
    Eigen::Vector3f pickOrigin;
268
    Eigen::Vector3f pickRay;
269
    double sinAngle2Closest;
270
    double when;
271
};
272

273
StarPicker::StarPicker(const Eigen::Vector3f& _pickOrigin,
274
                       const Eigen::Vector3f& _pickRay,
275
                       double _when,
276
                       float angle) :
277
    pickedStar(nullptr),
278
    pickOrigin(_pickOrigin),
279
    pickRay(_pickRay),
280
    sinAngle2Closest(std::max(std::sin(angle / 2.0), ANGULAR_RES)),
281
    when(_when)
282
{
283
}
284

285
void
286
StarPicker::process(const Star& star, float /*unused*/, float /*unused*/)
287
{
288
    Eigen::Vector3f relativeStarPos = star.getPosition() - pickOrigin;
289
    Eigen::Vector3f starDir = relativeStarPos.normalized();
290

291
    double sinAngle2 = 0.0;
292

293
    // Stars with orbits need special handling
294
    float orbitalRadius = star.getOrbitalRadius();
295
    if (orbitalRadius != 0.0f)
296
    {
297
        float distance = 0.0f;
298

299
        // Check for an intersection with orbital bounding sphere; if there's
300
        // no intersection, then just use normal calculation.  We actually test
301
        // intersection with a larger sphere to make sure we don't miss a star
302
        // right on the edge of the sphere.
303
        if (math::testIntersection(Eigen::ParametrizedLine<float, 3>(Eigen::Vector3f::Zero(), pickRay),
304
                                   math::Spheref(relativeStarPos, orbitalRadius * 2.0f),
305
                                   distance))
306
        {
307
            Eigen::Vector3d starPos = star.getPosition(when).toLy();
308
            starDir = (starPos - pickOrigin.cast<double>()).cast<float>().normalized();
309
        }
310
    }
311

312
    Eigen::Vector3f starMiss = starDir - pickRay;
313
    Eigen::Vector3d sMd = starMiss.cast<double>();
314
    sinAngle2 = sMd.norm() / 2.0;
315

316
    if (sinAngle2 <= sinAngle2Closest)
317
    {
318
        sinAngle2Closest = std::max(sinAngle2, ANGULAR_RES);
319
        pickedStar = &star;
320
        if (pickedStar->getOrbitBarycenter() != nullptr)
321
            pickedStar = pickedStar->getOrbitBarycenter();
322
    }
323
}
324

325
class CloseStarPicker : public engine::StarHandler
326
{
327
public:
328
    CloseStarPicker(const UniversalCoord& pos,
329
                    const Eigen::Vector3f& dir,
330
                    double t,
331
                    float _maxDistance,
332
                    float angle);
333
    ~CloseStarPicker() = default;
334
    void process(const Star& star, float lowPrecDistance, float appMag) override;
335

336
public:
337
    UniversalCoord pickOrigin;
338
    Eigen::Vector3f pickDir;
339
    double now;
340
    float maxDistance;
341
    const Star* closestStar;
342
    float closestDistance;
343
    double sinAngle2Closest;
344
};
345

346
CloseStarPicker::CloseStarPicker(const UniversalCoord& pos,
347
                                 const Eigen::Vector3f& dir,
348
                                 double t,
349
                                 float _maxDistance,
350
                                 float angle) :
351
    pickOrigin(pos),
352
    pickDir(dir),
353
    now(t),
354
    maxDistance(_maxDistance),
355
    closestStar(nullptr),
356
    closestDistance(0.0f),
357
    sinAngle2Closest(std::max(std::sin(angle/2.0), ANGULAR_RES))
358
{
359
}
360

361
void
362
CloseStarPicker::process(const Star& star,
363
                         float lowPrecDistance,
364
                         float /*unused*/)
365
{
366
    if (lowPrecDistance > maxDistance)
367
        return;
368

369
    Eigen::Vector3d hPos = star.getPosition(now).offsetFromKm(pickOrigin);
370
    Eigen::Vector3f starDir = hPos.cast<float>();
371

372
    float distance = 0.0f;
373

374
     if (math::testIntersection(Eigen::ParametrizedLine<float, 3>(Eigen::Vector3f::Zero(), pickDir),
375
                                math::Spheref(starDir, star.getRadius()), distance))
376
    {
377
        if (distance > 0.0f)
378
        {
379
            if (closestStar == nullptr || distance < closestDistance)
380
            {
381
                closestStar = &star;
382
                closestDistance = starDir.norm();
383
                sinAngle2Closest = ANGULAR_RES;
384
                // An exact hit--set the angle to "zero"
385
            }
386
        }
387
    }
388
    else
389
    {
390
        // We don't have an exact hit; check to see if we're close enough
391
        float distance = starDir.norm();
392
        starDir.normalize();
393
        Eigen::Vector3f starMiss = starDir - pickDir;
394
        Eigen::Vector3d sMd = starMiss.cast<double>();
395

396
        double sinAngle2 = sMd.norm() / 2.0;
397

398
        if (sinAngle2 <= sinAngle2Closest &&
399
            (closestStar == nullptr || distance < closestDistance))
400
        {
401
            closestStar = &star;
402
            closestDistance = distance;
403
            sinAngle2Closest = std::max(sinAngle2, ANGULAR_RES);
404
        }
405
    }
406
}
407

408
class DSOPicker : public engine::DSOHandler
409
{
410
public:
411
    DSOPicker(const Eigen::Vector3d& pickOrigin,
412
              const Eigen::Vector3d& pickDir,
413
              std::uint64_t renderFlags,
414
              float angle);
415
    ~DSOPicker() = default;
416

417
    void process(const std::unique_ptr<DeepSkyObject>&, double, float) override; //NOSONAR
418

419
public:
420
    Eigen::Vector3d pickOrigin;
421
    Eigen::Vector3d pickDir;
422
    std::uint64_t renderFlags;
423

424
    const DeepSkyObject* pickedDSO;
425
    double  sinAngle2Closest;
426
};
427

428
DSOPicker::DSOPicker(const Eigen::Vector3d& pickOrigin,
429
                     const Eigen::Vector3d& pickDir,
430
                     std::uint64_t renderFlags,
431
                     float angle) :
432
    pickOrigin      (pickOrigin),
433
    pickDir         (pickDir),
434
    renderFlags     (renderFlags),
435
    pickedDSO       (nullptr),
436
    sinAngle2Closest(std::max(std::sin(angle / 2.0), ANGULAR_RES))
437
{
438
}
439

440
void
441
DSOPicker::process(const std::unique_ptr<DeepSkyObject>& dso, double, float) //NOSONAR
442
{
443
    if (!(dso->getRenderMask() & renderFlags) || !dso->isVisible() || !dso->isClickable())
444
        return;
445

446
    Eigen::Vector3d relativeDSOPos = dso->getPosition() - pickOrigin;
447
    Eigen::Vector3d dsoDir = relativeDSOPos;
448

449
    if (double distance2 = 0.0;
450
        math::testIntersection(Eigen::ParametrizedLine<double, 3>(Eigen::Vector3d::Zero(), pickDir),
451
                               math::Sphered(relativeDSOPos, (double) dso->getRadius()), distance2))
452
    {
453
        Eigen::Vector3d dsoPos = dso->getPosition();
454
        dsoDir = dsoPos * 1.0e-6 - pickOrigin;
455
    }
456
    dsoDir.normalize();
457

458
    Eigen::Vector3d dsoMissd   = dsoDir - pickDir;
459
    double sinAngle2 = dsoMissd.norm() / 2.0;
460

461
    if (sinAngle2 <= sinAngle2Closest)
462
    {
463
        sinAngle2Closest = std::max(sinAngle2, ANGULAR_RES);
464
        pickedDSO        = dso.get();
465
    }
466
}
467

468
class CloseDSOPicker : public engine::DSOHandler
469
{
470
public:
471
    CloseDSOPicker(const Eigen::Vector3d& pos,
472
                   const Eigen::Vector3d& dir,
473
                   std::uint64_t renderFlags,
474
                   double maxDistance,
475
                   float);
476
    ~CloseDSOPicker() = default;
477

478
    void process(const std::unique_ptr<DeepSkyObject>& dso, double distance, float appMag); //NOSONAR
479

480
public:
481
    Eigen::Vector3d  pickOrigin;
482
    Eigen::Vector3d  pickDir;
483
    std::uint64_t renderFlags;
484
    double    maxDistance;
485

486
    const DeepSkyObject* closestDSO;
487
    double largestCosAngle;
488
};
489

490
CloseDSOPicker::CloseDSOPicker(const Eigen::Vector3d& pos,
491
                               const Eigen::Vector3d& dir,
492
                               std::uint64_t renderFlags,
493
                               double maxDistance,
494
                               float /*unused*/) :
495
    pickOrigin     (pos),
496
    pickDir        (dir),
497
    renderFlags    (renderFlags),
498
    maxDistance    (maxDistance),
499
    closestDSO     (nullptr),
500
    largestCosAngle(-2.0)
501
{
502
}
503

504
void
505
CloseDSOPicker::process(const std::unique_ptr<DeepSkyObject>& dso, //NOSONAR
506
                        double distance,
507
                        float /*unused*/)
508
{
509
    if (distance > maxDistance || !(dso->getRenderMask() & renderFlags) || !dso->isVisible() || !dso->isClickable())
510
        return;
511

512
    double  distanceToPicker       = 0.0;
513
    double  cosAngleToBoundCenter  = 0.0;
514
    if (dso->pick(Eigen::ParametrizedLine<double, 3>(pickOrigin, pickDir), distanceToPicker, cosAngleToBoundCenter))
515
    {
516
        // Don't select the object the observer is currently in:
517
        if ((pickOrigin - dso->getPosition()).norm() > dso->getRadius() &&
518
            cosAngleToBoundCenter > largestCosAngle)
519
        {
520
            closestDSO      = dso.get();
521
            largestCosAngle = cosAngleToBoundCenter;
522
        }
523
    }
524
}
525

526
void
527
getLocationsCompletion(std::vector<std::string>& completion,
528
                       std::string_view s,
529
                       const Body& body)
530
{
531
    auto locations = GetBodyFeaturesManager()->getLocations(&body);
532
    if (!locations.has_value())
533
        return;
534

535
    for (const auto location : *locations)
536
    {
537
        const std::string& name = location->getName(false);
538
        if (UTF8StartsWith(name, s))
539
        {
540
            completion.push_back(name);
541
        }
542
        else
543
        {
544
            const std::string& lname = location->getName(true);
545
            if (lname != name && UTF8StartsWith(lname, s))
546
                completion.push_back(lname);
547
        }
548
    }
549
}
550

551
} // end unnamed namespace
552

553
// Needs definition of ConstellationBoundaries
554
Universe::~Universe() = default;
555

556
StarDatabase*
557
Universe::getStarCatalog() const
558
{
559
    return starCatalog.get();
560
}
561

562
void
563
Universe::setStarCatalog(std::unique_ptr<StarDatabase>&& catalog)
564
{
565
    starCatalog = std::move(catalog);
566
}
567

568
SolarSystemCatalog*
569
Universe::getSolarSystemCatalog() const
570
{
571
    return solarSystemCatalog.get();
572
}
573

574
void
575
Universe::setSolarSystemCatalog(std::unique_ptr<SolarSystemCatalog>&& catalog)
576
{
577
    solarSystemCatalog = std::move(catalog);
578
}
579

580
DSODatabase*
581
Universe::getDSOCatalog() const
582
{
583
    return dsoCatalog.get();
584
}
585

586
void
587
Universe::setDSOCatalog(std::unique_ptr<DSODatabase>&& catalog)
588
{
589
    dsoCatalog = std::move(catalog);
590
}
591

592
AsterismList*
593
Universe::getAsterisms() const
594
{
595
    return asterisms.get();
596
}
597

598
void
599
Universe::setAsterisms(std::unique_ptr<AsterismList>&& _asterisms)
600
{
601
    asterisms = std::move(_asterisms);
602
}
603

604
ConstellationBoundaries*
605
Universe::getBoundaries() const
606
{
607
    return boundaries.get();
608
}
609

610
void
611
Universe::setBoundaries(std::unique_ptr<ConstellationBoundaries>&& _boundaries)
612
{
613
    boundaries = std::move(_boundaries);
614
}
615

616
// Return the planetary system of a star, or nullptr if it has no planets.
617
SolarSystem*
618
Universe::getSolarSystem(const Star* star) const
619
{
620
    if (star == nullptr)
621
        return nullptr;
622

623
    auto starNum = star->getIndex();
624
    auto iter = solarSystemCatalog->find(starNum);
625
    return iter == solarSystemCatalog->end()
626
        ? nullptr
627
        : iter->second.get();
628
}
629

630
// A more general version of the method above--return the solar system
631
// that contains an object, or nullptr if there is no solar sytstem.
632
SolarSystem*
633
Universe::getSolarSystem(const Selection& sel) const
634
{
635
    switch (sel.getType())
636
    {
637
    case SelectionType::Star:
638
        return getSolarSystem(sel.star());
639

640
    case SelectionType::Body:
641
        {
642
            PlanetarySystem* system = sel.body()->getSystem();
643
            while (system != nullptr)
644
            {
645
                Body* parent = system->getPrimaryBody();
646
                if (parent != nullptr)
647
                    system = parent->getSystem();
648
                else
649
                    return getSolarSystem(Selection(system->getStar()));
650
            }
651
            return nullptr;
652
        }
653

654
    case SelectionType::Location:
655
        return getSolarSystem(Selection(sel.location()->getParentBody()));
656

657
    default:
658
        return nullptr;
659
    }
660
}
661

662
// Create a new solar system for a star and return a pointer to it; if it
663
// already has a solar system, just return a pointer to the existing one.
664
SolarSystem*
665
Universe::getOrCreateSolarSystem(Star* star) const
666
{
667
    auto starNum = star->getIndex();
668
    auto iter = solarSystemCatalog->lower_bound(starNum);
669
    if (iter != solarSystemCatalog->end() && iter->first == starNum)
670
        return iter->second.get();
671

672
    iter = solarSystemCatalog->emplace_hint(iter, starNum, std::make_unique<SolarSystem>(star));
673
    return iter->second.get();
674
}
675

676
const celestia::MarkerList&
677
Universe::getMarkers() const
678
{
679
    return markers;
680
}
681

682
void
683
Universe::markObject(const Selection& sel,
684
                     const celestia::MarkerRepresentation& rep,
685
                     int priority,
686
                     bool occludable,
687
                     celestia::MarkerSizing sizing)
688
{
689
    if (auto iter = std::find_if(markers.begin(), markers.end(),
690
                                 [&sel](const auto& m) { return m.object() == sel; });
691
        iter != markers.end())
692
    {
693
        // Handle the case when the object is already marked.  If the
694
        // priority is higher or equal to the existing marker, replace it.
695
        // Otherwise, do nothing.
696
        if (priority < iter->priority())
697
            return;
698
        markers.erase(iter);
699
    }
700

701
    celestia::Marker& marker = markers.emplace_back(sel);
702
    marker.setRepresentation(rep);
703
    marker.setPriority(priority);
704
    marker.setOccludable(occludable);
705
    marker.setSizing(sizing);
706
}
707

708
void
709
Universe::unmarkObject(const Selection& sel, int priority)
710
{
711
    auto iter = std::find_if(markers.begin(), markers.end(),
712
                             [&sel](const auto& m) { return m.object() == sel; });
713
    if (iter != markers.end() && priority >= iter->priority())
714
        markers.erase(iter);
715
}
716

717
void
718
Universe::unmarkAll()
719
{
720
    markers.clear();
721
}
722

723
bool
724
Universe::isMarked(const Selection& sel, int priority) const
725
{
726
    auto iter = std::find_if(markers.begin(), markers.end(),
727
                             [&sel](const auto& m) { return m.object() == sel; });
728
    return iter != markers.end() && iter->priority() >= priority;
729
}
730

731
Selection
732
Universe::pickPlanet(const SolarSystem& solarSystem,
733
                     const UniversalCoord& origin,
734
                     const Eigen::Vector3f& direction,
735
                     double when,
736
                     float /*faintestMag*/,
737
                     float tolerance) const
738
{
739
    double sinTol2 = std::max(std::sin(tolerance / 2.0), ANGULAR_RES);
740
    PlanetPickInfo pickInfo;
741

742
    Star* star = solarSystem.getStar();
743
    assert(star != nullptr);
744

745
    // Transform the pick ray origin into astrocentric coordinates
746
    Eigen::Vector3d astrocentricOrigin = origin.offsetFromKm(star->getPosition(when));
747

748
    pickInfo.pickRay = Eigen::ParametrizedLine<double, 3>(astrocentricOrigin, direction.cast<double>());
749
    pickInfo.sinAngle2Closest = 1.0;
750
    pickInfo.closestDistance = 1.0e50;
751
    pickInfo.closestApproxDistance = 1.0e50;
752
    pickInfo.closestBody = nullptr;
753
    pickInfo.jd = when;
754
    pickInfo.atanTolerance = (float) atan(tolerance);
755

756
    // First see if there's a planet|moon that the pick ray intersects.
757
    // Select the closest planet|moon intersected.
758
    traverseFrameTree(solarSystem.getFrameTree(), when, &ExactPlanetPickTraversal, pickInfo);
759

760
    if (pickInfo.closestBody != nullptr)
761
    {
762
        // Retain that body
763
        Body* closestBody = pickInfo.closestBody;
764

765
        // Check if there is a satellite in front of the primary body that is
766
        // sufficiently close to the pickRay
767
        traverseFrameTree(solarSystem.getFrameTree(), when, &ApproxPlanetPickTraversal, pickInfo);
768

769
        if (pickInfo.closestBody == closestBody)
770
            return  Selection(closestBody);
771
        // Nothing else around, select the body and return
772

773
        // Are we close enough to the satellite and is it in front of the body?
774
        if ((pickInfo.sinAngle2Closest <= sinTol2) &&
775
            (pickInfo.closestDistance > pickInfo.closestApproxDistance))
776
            return Selection(pickInfo.closestBody);
777
            // Yes, select the satellite
778
        else
779
            return  Selection(closestBody);
780
           //  No, select the primary body
781
    }
782

783
    // If no planet was intersected by the pick ray, choose the planet|moon
784
    // with the smallest angular separation from the pick ray.  Very distant
785
    // planets are likley to fail the intersection test even if the user
786
    // clicks on a pixel where the planet's disc has been rendered--in order
787
    // to make distant planets visible on the screen at all, their apparent
788
    // size has to be greater than their actual disc size.
789
    traverseFrameTree(solarSystem.getFrameTree(), when, &ApproxPlanetPickTraversal, pickInfo);
790

791
    if (pickInfo.sinAngle2Closest <= sinTol2)
792
        return Selection(pickInfo.closestBody);
793
    else
794
        return Selection();
795
}
796

797
Selection
798
Universe::pickStar(const UniversalCoord& origin,
799
                   const Eigen::Vector3f& direction,
800
                   double when,
801
                   float faintestMag,
802
                   float tolerance) const
803
{
804
    Eigen::Vector3f o = origin.toLy().cast<float>();
805

806
    // Use a high precision pick test for any stars that are close to the
807
    // observer.  If this test fails, use a low precision pick test for stars
808
    // which are further away.  All this work is necessary because the low
809
    // precision pick test isn't reliable close to a star and the high
810
    // precision test isn't nearly fast enough to use on our database of
811
    // over 100k stars.
812
    CloseStarPicker closePicker(origin, direction, when, 1.0f, tolerance);
813
    starCatalog->findCloseStars(closePicker, o, 1.0f);
814
    if (closePicker.closestStar != nullptr)
815
        return Selection(const_cast<Star*>(closePicker.closestStar));
816

817
    // Find visible stars expects an orientation, but we just have a direction
818
    // vector.  Convert the direction vector into an orientation by computing
819
    // the rotation required to map -Z to the direction.
820
    Eigen::Quaternionf rotation;
821
    rotation.setFromTwoVectors(-Eigen::Vector3f::UnitZ(), direction);
822

823
    StarPicker picker(o, direction, when, tolerance);
824
    starCatalog->findVisibleStars(picker,
825
                                  o,
826
                                  rotation.conjugate(),
827
                                  tolerance, 1.0f,
828
                                  faintestMag);
829
    if (picker.pickedStar != nullptr)
830
        return Selection(const_cast<Star*>(picker.pickedStar));
831
    else
832
        return Selection();
833
}
834

835
Selection
836
Universe::pickDeepSkyObject(const UniversalCoord& origin,
837
                            const Eigen::Vector3f& direction,
838
                            std::uint64_t renderFlags,
839
                            float faintestMag,
840
                            float tolerance) const
841
{
842
    Eigen::Vector3d orig = origin.toLy();
843
    Eigen::Vector3d dir = direction.cast<double>();
844

845
    CloseDSOPicker closePicker(orig, dir, renderFlags, 1e9, tolerance);
846

847
    dsoCatalog->findCloseDSOs(closePicker, orig, 1e9);
848
    if (closePicker.closestDSO != nullptr)
849
    {
850
        return Selection(const_cast<DeepSkyObject*>(closePicker.closestDSO));
851
    }
852

853
    Eigen::Quaternionf rotation;
854
    rotation.setFromTwoVectors(-Eigen::Vector3f::UnitZ(), direction);
855

856
    DSOPicker picker(orig, dir, renderFlags, tolerance);
857
    dsoCatalog->findVisibleDSOs(picker,
858
                                orig,
859
                                rotation.conjugate(),
860
                                tolerance,
861
                                1.0f,
862
                                faintestMag);
863
    if (picker.pickedDSO != nullptr)
864
        return Selection(const_cast<DeepSkyObject*>(picker.pickedDSO));
865
    else
866
        return Selection();
867
}
868

869
Selection
870
Universe::pick(const UniversalCoord& origin,
871
               const Eigen::Vector3f& direction,
872
               double when,
873
               std::uint64_t renderFlags,
874
               float  faintestMag,
875
               float  tolerance)
876
{
877
    Selection sel;
878

879
    if (renderFlags & Renderer::ShowPlanets)
880
    {
881
        closeStars.clear();
882
        getNearStars(origin, 1.0f, closeStars);
883
        for (const auto star : closeStars)
884
        {
885
            const SolarSystem* solarSystem = getSolarSystem(star);
886
            if (solarSystem != nullptr)
887
            {
888
                sel = pickPlanet(*solarSystem,
889
                                origin, direction,
890
                                when,
891
                                faintestMag,
892
                                tolerance);
893
                if (!sel.empty())
894
                    break;
895
            }
896
        }
897
    }
898

899
    if (sel.empty() && (renderFlags & Renderer::ShowStars))
900
    {
901
        sel = pickStar(origin, direction, when, faintestMag, tolerance);
902
    }
903

904
    if (sel.empty())
905
    {
906
        sel = pickDeepSkyObject(origin, direction, renderFlags, faintestMag, tolerance);
907
    }
908

909
    return sel;
910
}
911

912
// Search by name for an immediate child of the specified object.
913
Selection
914
Universe::findChildObject(const Selection& sel,
915
                          std::string_view name,
916
                          bool i18n) const
917
{
918
    switch (sel.getType())
919
    {
920
    case SelectionType::Star:
921
        if (const SolarSystem* sys = getSolarSystem(sel.star()); sys != nullptr)
922
        {
923
            PlanetarySystem* planets = sys->getPlanets();
924
            if (planets != nullptr)
925
                return Selection(planets->find(name, false, i18n));
926
        }
927
        break;
928

929
    case SelectionType::Body:
930
        // First, search for a satellite
931
        if (const PlanetarySystem* sats = sel.body()->getSatellites();sats != nullptr)
932
        {
933
            Body* body = sats->find(name, false, i18n);
934
            if (body != nullptr)
935
                return Selection(body);
936
        }
937

938
        // If a satellite wasn't found, check this object's locations
939
        if (Location* loc = GetBodyFeaturesManager()->findLocation(sel.body(), name, i18n);
940
            loc != nullptr)
941
        {
942
            return Selection(loc);
943
        }
944
        break;
945

946
    default:
947
        // Locations and deep sky objects have no children
948
        break;
949
    }
950

951
    return Selection();
952
}
953

954
// Search for a name within an object's context.  For stars, planets (bodies),
955
// and locations, the context includes all bodies in the associated solar
956
// system.  For locations and planets, the context additionally includes
957
// sibling or child locations, respectively.
958
Selection
959
Universe::findObjectInContext(const Selection& sel,
960
                              std::string_view name,
961
                              bool i18n) const
962
{
963
    const Body* contextBody = nullptr;
964

965
    switch (sel.getType())
966
    {
967
    case SelectionType::Body:
968
        contextBody = sel.body();
969
        break;
970

971
    case SelectionType::Location:
972
        contextBody = sel.location()->getParentBody();
973
        break;
974

975
    default:
976
        break;
977
    }
978

979
    // First, search for bodies...
980
    if (const SolarSystem* sys = getSolarSystem(sel); sys != nullptr)
981
    {
982
        if (const PlanetarySystem* planets = sys->getPlanets(); planets != nullptr)
983
        {
984
            if (Body* body = planets->find(name, true, i18n); body != nullptr)
985
                return Selection(body);
986
        }
987
    }
988

989
    // ...and then locations.
990
    if (contextBody != nullptr)
991
    {
992
        Location* loc = GetBodyFeaturesManager()->findLocation(contextBody, name, i18n);
993
        if (loc != nullptr)
994
            return Selection(loc);
995
    }
996

997
    return Selection();
998
}
999

1000
// Select an object by name, with the following priority:
1001
//   1. Try to look up the name in the star catalog
1002
//   2. Search the deep sky catalog for a matching name.
1003
//   3. Check the solar systems for planet names; we don't make any decisions
1004
//      about which solar systems are relevant, and let the caller pass them
1005
//      to us to search.
1006
Selection
1007
Universe::find(std::string_view s,
1008
               util::array_view<const Selection> contexts,
1009
               bool i18n) const
1010
{
1011
    if (starCatalog != nullptr)
1012
    {
1013
        Star* star = starCatalog->find(s, i18n);
1014
        if (star != nullptr)
1015
            return Selection(star);
1016
        star = starCatalog->find(ReplaceGreekLetterAbbr(s), i18n);
1017
        if (star != nullptr)
1018
            return Selection(star);
1019
    }
1020

1021
    if (dsoCatalog != nullptr)
1022
    {
1023
        DeepSkyObject* dso = dsoCatalog->find(s, i18n);
1024
        if (dso != nullptr)
1025
            return Selection(dso);
1026
        dso = dsoCatalog->find(ReplaceGreekLetterAbbr(s), i18n);
1027
        if (dso != nullptr)
1028
            return Selection(dso);
1029
    }
1030

1031
    for (const auto& context : contexts)
1032
    {
1033
        Selection sel = findObjectInContext(context, s, i18n);
1034
        if (!sel.empty())
1035
            return sel;
1036
    }
1037

1038
    return Selection();
1039
}
1040

1041
// Find an object from a path, for example Sol/Earth/Moon or Upsilon And/b
1042
// Currently, 'absolute' paths starting with a / are not supported nor are
1043
// paths that contain galaxies.  The caller may pass in a list of solar systems
1044
// to search for objects--this is roughly analgous to the PATH environment
1045
// variable in Unix and Windows.  Typically, the solar system will be one
1046
// in which the user is currently located.
1047
Selection
1048
Universe::findPath(std::string_view s,
1049
                   util::array_view<const Selection> contexts,
1050
                   bool i18n) const
1051
{
1052
    std::string_view::size_type pos = s.find('/', 0);
1053

1054
    // No delimiter found--just do a normal find.
1055
    if (pos == std::string_view::npos)
1056
        return find(s, contexts, i18n);
1057

1058
    // Find the base object
1059
    auto base = s.substr(0, pos);
1060
    Selection sel = find(base, contexts, i18n);
1061

1062
    while (!sel.empty() && pos != std::string_view::npos)
1063
    {
1064
        auto nextPos = s.find('/', pos + 1);
1065
        auto len = nextPos == std::string_view::npos
1066
                 ? s.size() - pos - 1
1067
                 : nextPos - pos - 1;
1068

1069
        auto name = s.substr(pos + 1, len);
1070

1071
        sel = findChildObject(sel, name, i18n);
1072

1073
        pos = nextPos;
1074
    }
1075

1076
    return sel;
1077
}
1078

1079
void
1080
Universe::getCompletion(std::vector<std::string>& completion,
1081
                        std::string_view s,
1082
                        util::array_view<const Selection> contexts,
1083
                        bool withLocations) const
1084
{
1085
    // Solar bodies first:
1086
    for (const Selection& context : contexts)
1087
    {
1088
        if (withLocations && context.getType() == SelectionType::Body)
1089
        {
1090
            getLocationsCompletion(completion, s, *context.body());
1091
        }
1092

1093
        const SolarSystem* sys = getSolarSystem(context);
1094
        if (sys != nullptr)
1095
        {
1096
            const PlanetarySystem* planets = sys->getPlanets();
1097
            if (planets != nullptr)
1098
                planets->getCompletion(completion, s);
1099
        }
1100
    }
1101

1102
    // Deep sky objects:
1103
    if (dsoCatalog != nullptr)
1104
        dsoCatalog->getCompletion(completion, s);
1105

1106
    // and finally stars;
1107
    if (starCatalog != nullptr)
1108
        starCatalog->getCompletion(completion, s);
1109
}
1110

1111
void
1112
Universe::getCompletionPath(std::vector<std::string>& completion,
1113
                            std::string_view s,
1114
                            util::array_view<const Selection> contexts,
1115
                            bool withLocations) const
1116
{
1117
    std::string_view::size_type pos = s.rfind('/', s.length());
1118

1119
    if (pos == std::string_view::npos)
1120
    {
1121
        getCompletion(completion, s, contexts, withLocations);
1122
        return;
1123
    }
1124

1125
    auto base = s.substr(0, pos);
1126
    Selection sel = findPath(base, contexts, true);
1127

1128
    if (sel.empty())
1129
    {
1130
        return;
1131
    }
1132

1133
    if (sel.getType() == SelectionType::DeepSky)
1134
    {
1135
        completion.push_back(dsoCatalog->getDSOName(sel.deepsky()));
1136
        return;
1137
    }
1138

1139
    const PlanetarySystem* worlds = nullptr;
1140
    if (sel.getType() == SelectionType::Body)
1141
    {
1142
        worlds = sel.body()->getSatellites();
1143
    }
1144
    else if (sel.getType() == SelectionType::Star)
1145
    {
1146
        const SolarSystem* ssys = getSolarSystem(sel.star());
1147
        if (ssys != nullptr)
1148
            worlds = ssys->getPlanets();
1149
    }
1150

1151
    if (worlds != nullptr)
1152
        worlds->getCompletion(completion, s.substr(pos + 1), false);
1153

1154
    if (sel.getType() == SelectionType::Body && withLocations)
1155
    {
1156
        getLocationsCompletion(completion,
1157
                               s.substr(pos + 1),
1158
                               *sel.body());
1159
    }
1160
}
1161

1162
// Return the closest solar system to position, or nullptr if there are no planets
1163
// with in one light year.
1164
SolarSystem*
1165
Universe::getNearestSolarSystem(const UniversalCoord& position) const
1166
{
1167
    Eigen::Vector3f pos = position.toLy().cast<float>();
1168
    ClosestStarFinder closestFinder(1.0f, this);
1169
    closestFinder.withPlanets = true;
1170
    starCatalog->findCloseStars(closestFinder, pos, 1.0f);
1171
    return getSolarSystem(closestFinder.closestStar);
1172
}
1173

1174
void
1175
Universe::getNearStars(const UniversalCoord& position,
1176
                       float maxDistance,
1177
                       std::vector<const Star*>& nearStars) const
1178
{
1179
    Eigen::Vector3f pos = position.toLy().cast<float>();
1180
    NearStarFinder finder(maxDistance, nearStars);
1181
    starCatalog->findCloseStars(finder, pos, maxDistance);
1182
}
1183