Data structure for CAD program. Mouse picking and rendering with one data

Question

I try to implement my little CAD and wondering how to organize data for Bezier cubic surface primitives. My primitieves, for example a box, will contain six cubic Bezie patches, which constructes apartelly each other by own data for convenience. Any patch has 16 points. My primitieves will stitched for any iteraction (selecting points): for example any point on edge of patches will share own position with correspondong point of neighbor patches. I could delete duplicated points, but for rendering and updating primitieves I need remain the data untouched and the same time I need robust mouse picking algorithm which pick this points on edges and let move the one point together with corresponding points of neighbor patches. And I think I have two options:

1. Organizing data as std::multimap or something else where a few points will take linking through keys, but here I'll have problems with searching the points.
2. Improving the picking algorithm which provide picking 2-3 points as the one point, but I think it's a bad solution.

What is an common way to solve this problem? Thanks for any advice.

Answer 1

One common and relatively simple way is a pointer or index-based data structure. Example for the latter one:

std::vector<Vector3> vertices;
struct Patch
{
    // Zero-based indices of the 16 control points in the vertices vector
    uint32_t indices[4][4];
}
std::vector<Patch> patches;

One downside it’s expensive to erase vertices, because the patches need to be fixed adjusting these indices. Another downside it’s expensive to enumerate patches that link to a specific vertex, but if you need to do that often, you can build & maintain a separate index for that, e.g. std::unordered_multimap<uint32_t, uint32_t> lookupPatches;

This has the upside if you’re tessellating these Bézier patches on GPU, it's very efficient to upload both vertices (vertex buffer) and patches (index buffer). E.g. for D3d11, it's Map, memcpy, Unmap.