search

JuliaGeometry / GeometryBasics.jl

Basic Geometry Types
MIT License
165 stars 54 forks source link

Slim down GeometryBasics and remove all type complexity #173

Open SimonDanisch opened 2 years ago

SimonDanisch commented 2 years ago

So... I tried for a very long time to create a Geometry package that serves all use cases and can be used as a foundation for all other Geometry packages without any performance problems for any domain. This never really worked out for a bunch of reasons. While GeometryBasics was never used that way, all the ideal requirements I aimed for have turned GeometryBasics into a very overengineered package, with long compile times and complex types. I never really had a lot of time to actually maintain and grow it though, so on top of being overly complex it has been poorly documented. I also tried to integrate lots of types like LineStrings, which I don't know very well and when to use them :D So, this PR is slimming down GeometryBasics to the very basics that I need in Makie, which should help a lot with compile times and maintainability.

It changes:

Fixes:

Will not be in the scope of this package anymore:

evetion commented 2 years ago

This is some good cleanup! This is on top of #169 right?

Over at https://github.com/JuliaGeo/GeoInterface.jl/pull/33, we're now (finally) finishing a new Traits based interface. This gets rid of all the required subtyping on GeoInterface.Geometries and I would like to update the GeoInterface implementation in GeometryBasics here as well.

In that context, I see you removed LineString and changed the decomposition in this PR. In GeoInterface we still assume a Polygon decomposes into 1 or multiple LineStrings like instances (exterior ring and any interiors), which themselves decompose into Pointlikes. Do you think we could still make that work in this PR? Would Line be a proper replacement, or is it just two points?

SimonDanisch commented 2 years ago

Yes, I think we can bring it back, if we document a bit better what its supposed to be used for! I think we should keep them as simple as possible, so maybe something like:

struct LineString{N, T}
   line::Vector{Point{N, T}}
end

struct MultiLineString{N, T}
   lines::Vector{LineString{N, T}}
end
evetion commented 2 years ago

@SimonDanisch Is it ok to revive https://github.com/JuliaGeometry/GeometryBasics.jl/compare/master...visr:rfc?expand=1 on the current master of GeometryBasics? Or would you like me to open a PR, based on the changes in this PR? Also depends on your expected timeline of this PR?

SimonDanisch commented 2 years ago

No, that sounds great :) Looks like it has 0 dependencies, so that makes things a lot easier ;) I think master is fine... It's such a small diff, that it should be easy enough to rebase in this PR.

evetion commented 2 years ago

No, that sounds great :) Looks like it has 0 dependencies, so that makes things a lot easier ;) I think master is fine... It's such a small diff, that it should be easy enough to rebase in this PR.

Ok 👍🏻 , I've made a first attempt over at #175.

jeremiahpslewis commented 2 years ago

@SimonDanisch Is this PR still active? From its description, it would solve some issues with adding GeoInterface support to GeoMakie.

SimonDanisch commented 2 years ago

Yeah, still planning to merge it! Need to first make sure that Makie works though, which is a work in progress: https://github.com/JuliaPlots/Makie.jl/pull/2220

SimonDanisch commented 9 months ago
  1. Good question, I think I introduced that so that one can differentiate between primitives in GeometryBasics and outside... It's been a while, but I think I expected other packages to directly inherit from AbstractGeometry, or their own abstract subtype.
  2. It depends a lot on the type - there isn't a clear interface. Maybe we should have one though.
  3. In OpenGL you almost always have faces + points, so for this refactor I simplified it to always have the indices. For Polygons you shouldn't share points that much... I think a Polygon quickly becomes invalid if you share points?
  4. There isn't really any interaction beyond that MatNf + VecNf can be directly used as Uniforms via GLAbstraction.
rafaqz commented 9 months ago

Yes for 3, in most other geometry frameworks points are embedded in the polygon object.

Accessing indexed points is slower due to the indirection, and needs ~50% more memory in the (2d) case that no points are shared. It would only occasionally save ~25% memory when all points are shared between 2 polygons.

termi-official commented 9 months ago

Thanks for the elaborations. I will answer separately.

2. It depends a lot on the type - there isn't a clear interface. Maybe we should have one though.

Should we discuss this here on in a separate issue or here?

3. In OpenGL you almost always have faces + points, so for this refactor I simplified it to always have the indices. For Polygons you shouldn't share points that much... I think a Polygon quickly becomes invalid if you share points?

Why should they become invalid? For grid-based simulation technique this is very common. Think e.g. about the surface of a Hexahedral mesh as in the second figure in https://ferrite-fem.github.io/FerriteViz.jl/dev/atopics.html#High-order-fields . I guess it is assumed in the code that the polygon is strictly planar?

Accessing indexed points is slower due to the indirection, and needs ~50% more memory in the (2d) case that no points are shared. It would only occasionally save ~25% memory when all points are shared between 2 polygons.

Indeed a good point. But this changes drastically if we attach more meta information to the polygons.

From reading the code I get the impression that a mesh is required to be triangulated. I.e. we cant have a mesh with polygonal or polytopal elements, right?

Kevin-Mattheus-Moerman commented 4 months ago

@SimonDanisch @termi-official @rafaqz would it be worth resuming this discussion or has this gone stale? I am a new user but heavily invested now in GeometryBasics so would welcome and improvements like discussed here.

I can add to the discussion on this point by @termi-official:

Why do the polygons carry the points (in contrast to the mesh carrying a point vector and the polygons carry indices to this vector)?

I can see @rafaqz 's point that in some cases not shipping the points is inefficient (indexing takes time). But in computational methods (physics, engineering, finite element analysis) and geometry processing, this is really annoying and makes coding very inefficient. For instance shared nodes should be shared. If each face/element has its own points it may be convenient for rendering/visualisation, but when adjacent entities should share nodes this approach creates an excess of points that are really not needed. And this would also separate the entities that should really be attached (share points). This causes users to have to merge and split points repeatedly which makes every processing step very inefficient. Below I illustrate this problem with the help of a helpless bunny rabbit, left is imported STL (where each face has its own points), on the right after merging points are properly shared). So it sounds like we have users/requirements for both of these approaches (1) just indices, 2) ship with points) so perhaps GeometryBasics should support both?

https://github.com/JuliaGeometry/GeometryBasics.jl/assets/8392709/402e0146-93c5-49ea-ac0d-63fd7b72368d

For context, I am the developer for Comodo and just posted this related issue (before finding this PR): https://github.com/JuliaGeometry/GeometryBasics.jl/issues/217

ffreyer commented 1 month ago

Let me add some wishes/TODOs:

An obj file can reference an mtl file which contains material information such as lighting coefficients and paths to texture images (possibly including normals maps, specular maps, etc). These are then referenced by the obj file for groups of faces. To support that we would need:

If we want to support skeletal animation at some point we need:

Some other thoughts:

ffreyer commented 1 month ago

Another thing I forgot to mention is the issue of vertex duplication to get flat shading. E.g. that Rect is duplicating every vertex 3 times so that the corresponding normal can be different for each connected QuadFace. The way we are handling this atm means that even without normals, positions get duplicated. That has been annoying me with bounding boxes in Makie and I assume that is also an annoyance for Geometry related work. (Related #139)

A potential fix for this (specifically avoiding position duplication when vertex duplication is necessary) could be to allow faces() to output different indices for positions, normals and uvs. E.g.:

function faces(obj::Cylinder)
    pos_faces = # generate for position array
    normal_faces = # generate for normals array
    uv_faces = pos_faces
    return pos_faces, normal_faces, uv_faces
end

function create_normal_mesh(primitive)
    ps = coordinates(primitive)
    ns = normals(primitives)
    coord_fs, normal_fs, uv_fs = faces(primitive)
    if coord_fs === normal_fs
        return Mesh(ps, coord_fs; normals = ns)
    else
        fs, mappings = merge_faces(coord_fs, normal_fs) # remap with duplication
        ps = ps[mappings[1]]
        ns = ns[mappings[2]]
        return Mesh(ps, fs; normals = ns)
    end
end

where merge_faces would be this function that's currently sitting in MeshIO: https://github.com/JuliaIO/MeshIO.jl/blob/cb8e494a61a7b4458cbe6274ac75cf4ba91513e1/src/util.jl#L13. This way we could have meshes with only positions as well as coordinates() and texturecoordinates() skip the duplication, but generating a normal_mesh would be more expensive.

ffreyer commented 1 month ago

Regarding the Mesh type(s), bundling vertex attributes with a "basic" mesh and sub-mesh/global attributes with a more complex wrapper seems reasonable to me. E.g.

struct Mesh{
        # Dim, ElType <: Real, # are these useful to expose?
        PointType <: AbstractPoint, # allow other Point types
        PointCollection <: AbstractArray{PointType}, # maybe to allow GPU Arrays?
        FaceType <: AbstractFace
    }
    positions::PointCollection
    faces::Vector{FaceType}
    # per vertex data, e.g. normals, uvs, colors, ...
    vertex_meta::Dict{Symbol, AbstractVector}
end

struct MetaMesh{..., MT <: Mesh{...}} <: AbstractMesh
    # maybe a merged mesh from multiple submeshes
    mesh::MT

    # index ranges for mesh.faces which correspond to
    # one submesh
    submesh_views::Vector{UnitRange{UInt32}}

    # non-vertex data, either per submesh or fully global
    meta::Dict{Symbol, Any}
end

I don't think it's necessary to separate per-submesh (e.g. diffuse multiplier) and global data (e.g. a texture image) because I currently imagine these would be handled rather explicitly. For rendering I think it's optimal to upload all the vertices and faces once and then draw different sections by specifying different start pointers + counts, updating the necessary uniforms in between.

termi-official commented 1 month ago

If we want to support skeletal animation at some point we need:

* a bone-tree so we know how the bone matrices depend on each other

* per vertex bone indices and weights (probably just a vec4 each)

* maybe a cache for bone transformation matrices

Really like the idea of having functionality for skeletal animation in Julia. However, should this really go into GeometryBasics.jl? I would have rather thought that this is something for a separate package.

ffreyer commented 1 month ago

I only skimmed the learnopengl tutorial so far, so my understanding might be a bit off. But I think a good chunk of the data is closely related to a mesh. Weights and bone indices are vertex attributes, which would already be supported by the current GeometryBasics. The bone tree gives context to the bone indices and describes how the bone transforms inherit from each other. Data-wise I think it's debatable if that should be part of a mesh. My main motivation for wanting compatibility for it is that MeshIO may eventually be able to load it and I'd like it to still just return a mesh. In terms of functionality I don't think GeometryBasics should do much. I really just want it to be able hold all the data that mesh file formats store so they can be used somewhere else.