• detect 와 updateGraph 가 매우 중요

1. Place2dSegmenter::detect 관련

surface_places_->detect(input, *last_mesh_update_, *dsg_->graph);

• 이 코드는 2D 공간에서 장소(places)를 감지하고 그래프에 추가하는 과정을 다룹니다.
• 여러 단계에 걸쳐 장소를 감지하고, 특정 기준에 따라 장소를 분할하며, 최종적으로 유효한 장소들을 그래프에 반영하는 구조

요약

1. detect 함수는 활성화된 메시 인덱스를 기반으로 2D 장소를 감지하고, 이를 라벨별로 필터링하여 최종 장소를 생성하는 과정

• getActivePlaceIndices 함수는
  • 기존의 활성 장소와 새로 감지된 장소를 조합하여 유효한 인덱스들을 필터링
• findPlaces 함수는
  • 클러스터링을 통해 장소 후보들을 생성하고, 경계 정보를 업데이트
• decomposePlaces 함수는
  • 초기 장소를 더 작은 단위로 분해하여 최종적으로 유효한 장소들을 반환하는 역할
• 이러한 과정을 통해 2D 환경에서 장소를 감지하고, 이를 세밀하게 분해 및 업데이트

1. Place2dSegmenter::detect

• 이 함수는 주어진 MeshDelta와 DynamicSceneGraph를 바탕으로, 활성화된 장소들을 감지하는 핵심 함수

로직:

1. 활성화된 인덱스 가져오기:

   • 먼저 메시 델타에서 활성화된 인덱스를 가져오고, 이를 getActivePlaceIndices 함수를 통해 처리
   • 여기서 이미 그래프에 추가된 장소와 새로 감지된 인덱스 사이에서 유효한 장소들을 필터링

   const auto active_indices = getActivePlaceIndices(mesh_delta.getActiveIndices(),
                                                     active_places_,
                                                     mesh_delta,
                                                     graph,
                                                     num_archived_vertices_,
                                                     nodes_to_remove_);

2. 라벨 인덱스 필터링:

   • 그래프에서 제공된 라벨 정보에 따라 필터링하여, 감지된 장소들 중에서 특정 라벨에 맞는 인덱스들만을 추출합니다.

   LabelIndices label_indices = getLabelIndices(mesh.labels, *active_indices);

3. 라벨별 클러스터링 및 분할:

   • 라벨별로 클러스터링을 수행하여 초기 장소 후보들을 얻습니다.
     • 그런 다음, 이 장소들 중 최소 크기 조건을 충족하는 것들만을 필터링
   • 이 과정에서 findPlaces 함수와 decomposePlaces 함수가 사용됩니다.
     • findPlaces: 같은 Label의 points를 clustering 해서 장소로 지정
     • decomposePlaces: 위 결과를 더 작은 조각으로 분해

   const auto initial_places = findPlaces(mesh.points,
                                          mesh_delta,
                                          label_indices.at(label),
                                          config.connection_ellipse_scale_factor);
   
   std::vector<Place2d> final_places =
       decomposePlaces(mesh.points,
                       initial_places,
                       config.pure_final_place_size,
                       config.min_final_place_points,
                       config.connection_ellipse_scale_factor);

4. 최종 감지된 장소 저장:

   • 최종적으로 감지된 장소들을 detected_label_places_에 저장하여 이후 그래프 업데이트에 사용될 수 있도록 합니다.

---

2. getActivePlaceIndices

const auto active_indices = getActivePlaceIndices(mesh_delta.getActiveIndices(),
                                                  active_places_,
                                                  mesh_delta,
                                                  graph,
                                                  num_archived_vertices_,
                                                  nodes_to_remove_);

이 함수는 활성화된 장소의 인덱스들을 필터링하여 유효한 장소의 인덱스들을 반환하는 역할

• update된 mesh에 따라
  • 유효하지 않게 된 장소 노드들을 제거하는 역할
  • 장소 노드와 연결된 Mesh 정보를 업데이트 하는 역할

로직:

1. 초기화:
   • 먼저, 메시 델타에서 삭제된 인덱스를 반영하고, 장소 노드의 메시 연결 정보를 업데이트
   • 이를 통해 유효하지 않은 인덱스는 삭제되고, 활성 상태가 유지된 장소 노드들만 남게 됩니다.
2. 프리징된 인덱스 필터링:
   • 프리징된 인덱스(삭제된 메시의 일부)는 필터링되어 유효하지 않은 인덱스로 처리됩니다. 그 외의 인덱스들만 active_indices에 추가됩니다.

3. getLabelIndices

LabelIndices label_indices = getLabelIndices(mesh.labels, *active_indices);

• 이 코드는 2D 세그멘테이션 작업에서 활성화된 인덱스의 라벨을 기반으로 필터링하는 과정

요약

• 이 함수의 목적:
  • 활성화된 인덱스들 중에서 유효한 라벨을 가진 인덱스들만 추출하고, 이를 라벨별로 그룹화하는 역할
• 최종적으로 필터링된 라벨-인덱스 매핑을 반환합니다. 각 라벨에 대해, 해당 라벨을 가지는 메시의 인덱스들을 저장한 맵입니다.

---

4. findPlaces

   const auto initial_places = findPlaces(mesh.points,
                                          mesh_delta,
                                          label_indices.at(label),
                                          config.connection_ellipse_scale_factor);

1. findPlaces 함수 개요

• 이 함수는 2D 메시의 클러스터링 작업을 수행하여 특정 라벨에 해당하는 인덱스들 중에서 물리적으로 가까운 포인트들을 그룹화하여 "장소(places)"로 정의
• 그 과정에서 각 장소의 기하학적 특성(예: 중심, 확장 행렬 등)을 계산하여 저장

---

• 구체적으로, 입력된 메시 포인트들의 인덱스(cloud_indices)를 받아서,
  • 클러스터링을 통해 장소를 탐지하고,
  • 각 장소의 기하학적 특징을 계산하여 반환
• 이 함수는 클러스터링된 각 장소에 대해 타원형(ellipse)을 맞추는 정보를 추가로 계산해 저장

4. 요약

• findPlaces 함수는 메시 데이터에서 특정 라벨에 해당하는 포인트들을 클러스터링하여 "장소"로 정의하는 과정
• 각 장소에 대해 타원형 근사를 통해 중심점, 확장 및 압축 행렬, 커팅 평면 등 공간적 기하학 정보를 계산하여 저장
• 타원 근사는 장소의 물리적 경계를 나타냅니다.

5. decomposePlaces

    std::vector<Place2d> final_places =
        decomposePlaces(mesh.points,
                        initial_places,
                        config.pure_final_place_size,
                        config.min_final_place_points,
                        config.connection_ellipse_scale_factor);

decomposePlaces 알고리즘 개요

• decomposePlaces 함수는 하나의 장소(Place)를 더 작은 서브 장소들로 재귀적으로 분해하는 과정을 수행
• 이 알고리즘은 공간 내 복잡한 형태나 큰 영역을 작은 단위로 나누어 관리하기 위해 설계
• 각 장소를 최적의 크기와 구조로 분할

3. 알고리즘의 장점과 활용

• 효율적인 공간 분할: 이 알고리즘은 장소를 재귀적으로 분해하여 탐색 및 맵핑에 유리한 작은 단위로 나눕니다.
• 경계 기반 분할: 각 장소의 경계를 정의하여, 인접한 장소 간의 관계를 더 잘 파악할 수 있습니다.
• 동적 조정 가능: 최소 크기(min_size)와 최소 포인트 수(min_points)를 조정하여, 원하는 수준의 분할을 수행할 수 있습니다.

---

4. 요약

• decomposePlaces 알고리즘은 장소를 재귀적으로 분할하고, 각 장소의 경계와 중심을 계산하여 최적의 공간 분할을 수행합니다.

• 재귀적 분해: 큰 장소를 더 작은 서브 장소로 분할

• 컨벡스 헐 계산: 장소의 경계와 중심을 정확하게 파악

1. 핵심 알고리즘 흐름

• decomposePlaces는 최소 크기(min_size)와 최소 포인트 수(min_points)를 기준으로, 장소를 재귀적으로 분할합니다. 이 함수는 다음과 같은 주요 단계를 따릅니다.

1. 입력된 각 장소에 대해 분할 수행:

   • 각 장소를 splitPlace 함수로 두 개의 서브 장소(자식 노드)로 나눕니다.
   • 이 과정은 타원의 장축(major axis)을 기준으로 두 영역을 나누는 형태입니다.

2. 분할된 장소가 충분히 작은지 확인:

   • 두 서브 장소가 각각 최소 크기(min_size)와 최소 포인트 수(min_points)를 만족하는지 확인합니다.
   • 만약 서브 장소가 너무 크다면, 해당 장소에 대해 재귀적으로 다시 분해합니다.

3. 모든 분해가 완료된 후, 장소에 경계 정보 추가:

   • 최종적으로 분해된 서브 장소마다 경계(convex hull) 정보를 계산하여 저장

---

2. updateGraph 메서드 관련

    surface_places_->detect(input, *last_mesh_update_, *dsg_->graph);
    {  // start graph critical section
      std::unique_lock<std::mutex> graph_lock(dsg_->mutex);

      surface_places_->updateGraph(input.timestamp_ns, input, *dsg_->graph);
      // TODO(nathan) unify places so that active places get populated correctly
      // depending on run configuration
    }  // end graph update critical section

    archivePlaces2d(active_nodes);

요약

• updateGraph 알고리즘은 2D 장소의 상태를 실시간으로 관리하여
  • 그래프의 일관성을 유지하고, 불필요한 데이터를 정리하며,
  • 중요한 장소 간의 연결성을 강화

updateGraph 알고리즘 개요

• Place2dSegmenter::updateGraph는 2D 장소를 동적으로 갱신

1. 오래되거나 비어 있는 노드를 제거하고,
2. 새로운 장소(places)를 그래프에 추가,
3. 활성(active), 준활성(semiactive), 비활성 노드 상태를 관리
4. 장소 간의 관계를 기반으로 엣지(edge)를 추가합니다.

핵심 목표와 역할

• 그래프에서 불필요한 노드 제거: 더 이상 유효하지 않은 장소를 정리하여 메모리와 계산 자원을 절약.
• 동적인 장소 추가 및 업데이트: 새로운 장소를 그래프에 반영하고 유지.
• 장소 간 관계 형성: 장소 간의 인접성을 바탕으로 엣지를 생성해 그래프의 연결성 강화
• 노드 상태 관리:
  • 노드의 활성/비활성 상태를 효율적으로 관리하여 데이터의 일관성을 유지.

1. 그래프에서 오래되거나 비어 있는 노드 제거

• dangling nodes(비어 있거나 유효하지 않은 노드)는 삭제됩니다.
• 노드가 더 이상 메시 연결(mesh connections)이 없거나 경계(boundary)가 3개 미만일 경우 불필요한 노드로 간주합니다.
• 또한, 아카이브된 인덱스와 연결된 노드도 삭제됩니다.
  • 아카이브된 인덱스는 이전에 사용되었지만 더 이상 최신 상태가 아닌 데이터를 의미

---

2. 장소 상태 확인 및 갱신

active_places_와 detected_label_places_를 기반으로 활성 노드 집합을 새롭게 계산합니다.
1. 위치 정보가 없을 때: 이전에 활성화된 모든 노드가 새롭게 활성화됩니다.
2. 위치 정보가 있을 때:

• 각 노드를 검사하여 아카이브되지 않은 노드만 활성 상태로 유지

3. 새로운 장소가 탐지된 경우:

• 해당 장소를 그래프에 추가합니다.
  이 단계에서 노드를 active_places_to_check와 new_active_places로 분류하여 갱신할 필요가 있는 노드만 처리합니다.

active_places_와 detected_label_places_

active_places_의 의미

• 현재 활성화된 장소 집합:
• 유지 및 관리:
  시간이 지남에 따라 장소의 상태를 평가하고, 여전히 유효한 장소만 포함합니다.
• 그래프에서의 지속성 보장:
  장소가 계속 유효하다면 유지되고, 그렇지 않으면 삭제되거나 다른 상태로 전환됩니다.

detected_label_places_의 의미

• 새롭게 탐지된 장소들:
  최신 탐지 과정에서 발견된 장소를 일시적으로 저장하는 데이터
• 그래프 반영 전 상태:
  탐지된 장소들은 아직 그래프에 추가되지 않은 상태로, 이 데이터에 임시 저장
• 업데이트 시 활용:
  그래프가 갱신될 때 이 정보가 반영되어 새로운 장소를 추가

3. 노드 간의 연결 형성 (엣지 생성)

• 이 단계에서는 활성 및 준활성 노드 간에 엣지를 추가하여 그래프의 연결성을 강화

1. 노드 간 연결을 시도:

   • 각 두 노드 쌍에 대해 frontendAddPlaceConnection을 호출합니다.
   • 이 함수는 두 노드가 특정 기준을 충족하는 경우 엣지를 추가합니다.

2. 이웃 노드 상태 검사:

   • 이웃 노드가 아카이브된 데이터와 연결되어 있다면,
   • 해당 노드는 여전히 불완전한 상태로 간주

frontendAddPlaceConnection (shouldAddPlaceConnection)

• 이 알고리즘은 단순한 유클리드 거리 기반 연결보다 훨씬 정밀한 연결 판단을 제공

두 장소 간 연결 여부 판단의 핵심 개념

1. 장소 간의 Overlap Distance(중첩 거리) 측정

• 두 장소를 각각 타원체(ellipsoid)로 모델링하여, 타원체의 겹침 정도를 계산
• ellipsoid overlap distance는 두 장소 간 타원의 중심을 따라 얼마나 겹치는지를 나타내는 지표입니다.
• 수치가 클수록 두 장소가 밀접하게 연결되어 있다고 판단할 수 있습니다.

2. 높이 차이(Centroid Height Offset) 측정

• 두 장소의 중심 높이(Z 축) 간의 절대 차이를 구합니다.
• 이는 두 장소가 수직적으로 얼마나 가까운지를 측정하는 역할을 합니다.
• 설정된 최대 높이 차이(place_max_neighbor_z_diff)를 넘지 않는지 확인하여, 물리적으로 연결될 수 있는지 평가합니다.

3. 조건에 따른 연결 여부 결정

• 두 장소 간 중첩 거리가 설정된 임계값(place_overlap_threshold) 이상이어야 합니다.
• 높이 차이가 설정된 최대 값 이하일 때만 연결을 생성합니다.
• 위 조건을 모두 만족할 경우, 두 장소 간에 연결을 추가할 필요가 있다고 판단합니다.

4. Edge Weight의 계산 및 부여

• 연결된 엣지에는 중첩 거리 값을 가중치(weight)로 부여
• 이 가중치는 그래프 내에서 두 장소 간의 연결 강도나 가까움을 표현하며, 추후 경로 탐색이나 네트워크 분석에 유용합니다.

4. 노드 상태 업데이트 (활성, 준활성, 비활성)

각 노드는 상태에 따라 활성(active), 준활성(semiactive), 비활성(inactive)으로 나뉩니다.

1. 활성 노드:

   • 아카이브된 인덱스와 관련이 없고, 모든 이웃이 고정된 상태일 경우.

2. 준활성 노드:

   • 아카이브된 인덱스와 관련된 포인트가 있지만, 여전히 중요한 장소인 경우.

3. 비활성 노드:

   • 더 이상 유효하지 않은 장소로 간주되는 경우.

이 정보를 바탕으로 노드를 active_places_와 semiactive_places_로 분류합니다.

---