Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Triangulator.triangulate out of memory error #737

Closed
dlcruz opened this issue Sep 11, 2019 · 2 comments
Closed

Triangulator.triangulate out of memory error #737

dlcruz opened this issue Sep 11, 2019 · 2 comments
Labels
bug
Milestone

Comments

@dlcruz
Copy link

@dlcruz dlcruz commented Sep 11, 2019

I ran into the following out of memory error calling panda.code's Triangulator.triangulate().

Out of memory allocating 17179869184 bytes
Aborted (core dumped)

I am able to reproduce this error with the snippet of code below:

from panda3d.core import LVector2
from panda3d.core import Triangulator

class Polygon:
    def __init__(self, points=None):
        self._triangulator = Triangulator()

        if points is not None:
            for point in points:
                self.add_poly_vertex(point)

    def add_poly_vertex(self, point):
        vertex_id = self._triangulator.addVertex(point.x, point.y)
        self._triangulator.addPolygonVertex(vertex_id)

    def create(self):
        self._triangulator.triangulate()

points = [
    LVector2(-0.07, 1.0),
    LVector2(-0.39, 0.88),
    LVector2(1.1, 0.97), 
    LVector2(0.9, 0.99), 
    LVector2(0.8, 0.9)]

polygon = Polygon(points=points)
polygon.create()

It looks like in triangulator::triangulate_single_polygon from panda/src/mathutil/triangulator.cxx there is a while loop which doesn't seem to terminate, and keeps pushing back to a vector, eventually hitting OOM.

@Moguri Moguri added the bug label Sep 16, 2019
@rdb

This comment has been minimized.

Copy link
Member

@rdb rdb commented Sep 18, 2019

Hi, thanks for the bug report!

Of course Panda should not be going in an infinite allocation loop here, but I do want to point out that the polygon in question is a very strangely self-overlapping polygon:
image

That said, maybe it's about time we replaced the triangulation algorithm with something simpler, such as ear clipping.

@rdb rdb added this to the 1.10.5 milestone Sep 18, 2019
@rdb

This comment has been minimized.

Copy link
Member

@rdb rdb commented Sep 18, 2019

I've checked in a workaround that will prevent Panda3D from entering an infinite loop and running out of memory. However, I believe the result will not be correct for an overlapping polygon like this.

I still think the triangulation algorithm must be replaced by something more robust, but I think that is a separate issue.

Thanks again for the report, and especially for the simple test case!

@rdb rdb closed this in 66b338c Sep 30, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
3 participants
You can’t perform that action at this time.