Ограниченная иерархия объема

Я строю иерархию ограниченных томов в Голанге. Я могу сказать, что мой код работает, потому что я сделал несколько тестов на нем, и он дает те же результаты, что и реализация грубой силы (грубая сила - проверить все возможности в \ $ O (n ^ 2) \ $).

Моя проблема в том, что код медленнее, чем реализация грубой силы (но не настолько, но достаточно, чтобы заставить меня задаться вопросом, почему я потрудился реализовать это в первую очередь). Возможно, это нормально, но мне хотелось бы, чтобы мои сверстники пришли к этому.

Для тех, кто не знает Голанга, но все равно хотел бы взглянуть. a chan - это примитив для отправки /получения сообщений из других потоков (мы называем thread, goroutine в Go). Если у меня есть c <- m, это означает «отправить это сообщение через этот канал». И грубая сила, и BVH используют этот примитив, поэтому, вероятно, это не причина замедления.

package tornago

// this line makes sure that *BVHNode is a valid Broadphase
var _ Broadphase = (*BVHNode)(nil)

// BVHNode represents a single node in a bounding volume hierarchy.
type BVHNode struct {
    children [2]*BVHNode
    parent   *BVHNode
    BoundingSphere
    body *RigidBody
}

// NewBVHNode returns a new bvh node. Use this to start a bvh tree.
func NewBVHNode(b *RigidBody, volume *BoundingSphere) BVHNode {
    return BVHNode{
        body:           b,
        BoundingSphere: *volume,
    }
}

// IsLeaf returns true if this node has no children.
func (n *BVHNode) IsLeaf() bool {
    return n.body != nil
}

// GeneratePotentialContacts sends all colliding bounding sphere to the narrow
// phase detector.
func (n *BVHNode) GeneratePotentialContacts(narrowPhaseDetector chan<- PotentialContact) {
    if n.IsLeaf() {
        return
    }
    n.children[0].GeneratePotentialContactsWith(n.children[1], narrowPhaseDetector)
}

// GeneratePotentialContactsWith accepts a second node with a bounding volume to
// test against.
func (n *BVHNode) GeneratePotentialContactsWith(o *BVHNode, narrowPhaseDetector chan<- PotentialContact) {
    //df("inspecting %p,%p\n", n, o)
    // If they don't overlap then we are done.
    if !n.Overlaps(&o.BoundingSphere) {
        return
    }

    // If they're both leaves, then we have a potential contact.
    if n.IsLeaf() && o.IsLeaf() {
        narrowPhaseDetector <- PotentialContact{
        [2]*RigidBody{n.body, o.body},
        }
        return
    }

    // Determine which node to descend into. If either is a leaf, then we
    // descend the other. If both are branches, then we use the one with the
    // largest size.
    if n.IsLeaf() {
        n.GeneratePotentialContactsWith(o.children[0], narrowPhaseDetector)
        n.GeneratePotentialContactsWith(o.children[1], narrowPhaseDetector)
        o.GeneratePotentialContacts(narrowPhaseDetector)
        return
    }

    if o.IsLeaf() {
        o.GeneratePotentialContactsWith(n.children[0], narrowPhaseDetector)
        o.GeneratePotentialContactsWith(n.children[1], narrowPhaseDetector)
        n.GeneratePotentialContacts(narrowPhaseDetector)
        return
    }

    // If they're both branches then descent into the biggest.
    if n.GetSize() < o.GetSize() {
        n.GeneratePotentialContactsWith(o.children[0], narrowPhaseDetector)
        n.GeneratePotentialContactsWith(o.children[1], narrowPhaseDetector)
        n.GeneratePotentialContacts(narrowPhaseDetector)
    } else {
        n.children[0].GeneratePotentialContactsWith(o, narrowPhaseDetector)
        n.children[1].GeneratePotentialContactsWith(o, narrowPhaseDetector)
        o.GeneratePotentialContacts(narrowPhaseDetector)
    }

    // and then like do them separatelly because yknow thats what things.
}

// RecalculateBoundingVolume recalculates the bounding sphere of this node.
func (n *BVHNode) RecalculateBoundingVolume() {
    if n.IsLeaf() {
        return
    }
    n.BoundingSphere = NewBoundingSphereFromSpheres(&n.children[0].BoundingSphere, &n.children[1].BoundingSphere)
    if n.parent != nil {
        n.parent.RecalculateBoundingVolume()
    }
}

// Insert inserts this rigid body in this node of one of it's childs.
func (n *BVHNode) Insert(b *RigidBody, volume *BoundingSphere) {
    if n.IsLeaf() {
        n.children[0] = &BVHNode{
            BoundingSphere: n.BoundingSphere,
            body:           n.body,
            parent:         n,
        }
        n.children[1] = &BVHNode{
            BoundingSphere: *volume,
            body:           b,
            parent:         n,
        }
        n.body = nil
        n.RecalculateBoundingVolume()
        return
    }

    if n.children[0].GetGrowth(volume) < n.children[1].GetGrowth(volume) {
        n.children[0].Insert(b, volume)
    } else {
        n.children[1].Insert(b, volume)
    }
}

Есть ли что-то очевидное в моей реализации, которое сделало бы это супер медленным? Я что-то делаю дважды или что-нибудь, что могло бы добавить намного больше работы для достижения того же результата?

10 голосов | спросил user2475269 28 PM00000070000000031 2015, 19:21:00

1 ответ


2

Поскольку вы говорите, что этот метод медленнее, чем механизм грубой силы O (n ^ 2) (также не показан), я могу только предположить, что вы имеете в виду для любого n.

Это означает, что ваш новый алгоритм также является алгоритмом \ $ O (n ^ 2) \ $. Фактически вы можете видеть в GeneratePotentialContactsWith, что это, по крайней мере, функция $ (ln (n)) \ $, так как она использовать рекурсию дерева; это может быть функция \ O (n) - мне это непонятно.

Вы не показываете свою функцию NewBoundingSphereFromSpheres, это тоже рекурсия? (давая другую функцию \ $ O (ln (n)) \ $ /\ $ O (n) \ $)

Если GeneratePotentialContactsWith или NewBoundingSphereFromSpheres a \ $ O (n) \ $, тогда обработка n точек даст алгоритм \ $ O (n ^ 2) \ $.

Обратите внимание, что если вы хотите получить максимальную производительность для данного алгоритма, тогда не используйте каналы. Они намного медленнее вызовов функций. Рекурсия петли также значительно быстрее, чем функция рекурсии, поскольку она позволяет избежать распределения стека и для инициализации каждой функции & выход из строя. Каналы обеспечивают элегантный параллелизм, но просто убедитесь, что вы максимизируете объем производительной работы и минимизируете объем выполняемой работы во время выполнения параллелизма канала, который невидимо выполняется.

ответил RidiculousRichard 22 AMpSun, 22 Apr 2018 01:09:57 +030009Sunday 2018, 01:09:57

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132