juliohull

[JoeJ]

Just noticed there is nothing more on https://code.google.com/archive/p/juliohull/, in case you want to move it to github.

Maybe you can give me some help using it.
Currently i have this:

Code: Select all

#ifdef USE_NEWTON_CONVEX_HULL

#include <../core/dgConvexHull3d.h>
#include <vector>

struct ConvexHull
{
   std::vector<dgFloat64> tempPointData;
   dgMemoryAllocator allocation;
   dgFloat64 volume;
   dgFloat64 surcafeArea;
   
   //dgConvexHull3d myhull; // no defasult constructor :(

   ConvexHull ()
   {
      volume = 0;
      surcafeArea = 0;
   }

   ~ConvexHull ()
   {
   }

   void AddVertex (float x, float y, float z)
   {
      tempPointData.push_back (dgFloat64(x));
      tempPointData.push_back (dgFloat64(y));
      tempPointData.push_back (dgFloat64(z));
   }

   bool BuildConvexHull ()
   {
      dgConvexHull3d myhull (&allocation, &tempPointData[0], sizeof(double)*3, tempPointData.size()/3, 0.0001, 200);
      myhull.CalculateVolumeAndSurfaceArea (volume, surcafeArea);
      return true;
   }

   float Volume ()
   {
      return fabs(volume);
   }
   float Area ()
   {
      return fabs(surcafeArea);
   }

   bool TraceRay (float &tMin, float &tMax, const float* rayO, const float *rayD) const
   {
      // todo: keep myhull, so i can ray trace rays

      //dgConvexHull3d::RayCast (const dgBigVector& localP0, const dgBigVector& localP1) const
   }

};


Being OOP noob, i don't know how to keep dgConvexHull3d around so i can use it for ray tracing later.

I'd like to declare the object as a member of my ConvexHull struct, but at this point i know nothing and can't provide data about the points.

Probably i could create dgConvexHull3d with new, store a pointer to it and use this for tracing, but i'm interested if there is another solution.

[Julio Jerez]

can't you use the function form the library? the dgCore is a stand along library

to use the convex hull all you nee to do is somethong like this

Code: Select all

dgMemoryAllocator  allocator;
const dgFloat64* vertexCloud;
dgInt32 strideInBytes = "the stride fo the vertex array in byte";
dgInt32 count = "vertex count";
dgFloat64 distTol = 1.0e-4;
dgInt32 maxVertexCount = "set to a any max number or max int"

dgConvexHull3d convexHull (&allocator, vertexCloud, strideInBytes, count, distTol, maxVertexCount);

then this inteface let you get the vertices

Code: Select all

   dgInt32 GetVertexCount() const;
   const dgBigVector* GetVertexPool() const;
   const dgBigVector& GetVertex(dgInt32 i) const;



and to get the faces you iterate ove the list of faces
like this

Code: Select all

for (dgList<dgConvexHull3DFace>::dgListNode* faceNode = convexHull.GetFirst(); faceNode; faceNode = faceNody->GetNext())
{
const   dgConvexHull3DFace& face = faceNode ->GetInfo();
// and th etrinagel indices are in
int i0 = face.m_index[0];
int i1 = face.m_index[1];
int i2 = face.m_index[2];
}

[Julio Jerez]

you keep a convex hull around you just use
new dgConvexHull3d (....)

for that you can create an allocator that you can use for all your work wit the dgCore library.
all closes or container in the dgCore library take an pool base allocator, that is independent of instances, so new intake do not create fragmentation for other instances. that's the difference wit the dContainerLibrary, which each container is its own allocator.
If this was fast enough I would use it for all, but it is not, Newton uses those container really hard and a series of calls of mallow and free is too slow for hundred of thousand of call per frame.

for example when the dNewtonClass is created. It take an allocator, and that allocator is use for all allocations of that instance. If another class is created, that one take a different allocator and so on.

[JoeJ]

Ok, thanks.
(I did not knew the allocator will be used for the creation of the object itself. So that's quite nice and i'll use one allocater for all then.)

[Julio Jerez]

no, no, no,
The allocation is used to allocate any internal data for the class, the class with no use the allocation fo the you need to create the object like this.
from file: ..\sdk\dgPhysics\dgCollisionConvexHull.cpp

Code: Select all

convexHull =  new (GetAllocator()) dgConvexHull3d (GetAllocator(), &buffer[0], 3 * sizeof (dgFloat64), count, tolerance);

this is why I said you can create an allocator, and use that for all class in the library,
this is why I said that each dgWorld object creates an allocator and pass it as the argument so that all object from a newton instance are created for the same allocator, eh world serve as the memory manager for all memory allocation of that instance

Code: Select all

// from file newton.cpp
NewtonWorld* NewtonCreate()
{
   TRACE_FUNCTION(__FUNCTION__);
   dgMemoryAllocator* const allocator = new dgMemoryAllocator();

   NewtonWorld* const world = (NewtonWorld*) new (allocator) Newton (dgFloat32(1.0f), allocator);
   return world;
}

you can do something similar, in one manager you create an allocator and you use it for all class in dgCore. There is a lot of good stuff in dgCore.
In fact I made my living using that class for over 20 years

[JoeJ]

Can you again take a look at my code?
Seems right to me, but never did overloading new(), so still unsure

header:

Code: Select all

struct ConvexHull
{
   std::vector<dgFloat64> tempPointData;
   static dgMemoryAllocator allocator;
   dgFloat64 volume;
   dgFloat64 surcafeArea;
   
   dgConvexHull3d *convexHull;

   ConvexHull ()
   {
      volume = 0;
      surcafeArea = 0;
      convexHull = 0;
   }

   ~ConvexHull ()
   {
      if (convexHull) delete convexHull; // no need to give allocater here ???
   }

   void AddVertex (const float x, const float y, const float z)
   {
      tempPointData.push_back (dgFloat64(x));
      tempPointData.push_back (dgFloat64(y));
      tempPointData.push_back (dgFloat64(z));
   }

   bool BuildConvexHull ()
   {
      convexHull =  new (&allocator) dgConvexHull3d (&allocator, &tempPointData[0], 3 * sizeof (dgFloat64), tempPointData.size()/3, 0.0001);
      if (convexHull)
      {
         convexHull->CalculateVolumeAndSurfaceArea (volume, surcafeArea);
         tempPointData.clear();
         return true;
      }
      return false;
   }

   

   bool TraceRay (float &tMin, float &tMax, const float* rayO, const float *rayD) const
   {
      if (convexHull)
      {
         dgBigVector bMin, bMax;
         convexHull->GetAABB(bMin, bMax);
         dgFloat64 mag = dgSqrt ( (bMin - bMax).DotProduct3(bMin - bMax) );

         dgBigVector rO ((dgFloat32*)rayO); rO.m_w = 1;
         dgBigVector rD ((dgFloat32*)rayD); rD.m_w = 0;

         tMax = (float) ((convexHull->RayCast (rO + rD.Scale3(mag), rO - rD.Scale3(mag)) * -2.0f + 1.0f) * mag);
         tMin = (float) ((convexHull->RayCast (rO - rD.Scale3(mag), rO + rD.Scale3(mag)) *  2.0f - 1.0f) * mag); // it would be nice if RayCast would expose tE and tL :)

         return true;
      }
      return false;
   }

};


cpp file:

Code: Select all

#ifdef USE_NEWTON_CONVEX_HULL
dgMemoryAllocator ConvexHull::allocator;
#endif


My raytracing interface is broken (EDIT: fixed), but anyways i need to do it twice because you bad guy do only expose the entry hitpoint but i want exit too

But there's more than that, so probably i need to hack your stuff a lot to speed things up.
I want those things:

A mapping from input vertex to hull vertex if it presists, or the hull polygon otherwise.

The abilty to add vertices after the hull is already computed.


Would this be easy too add?


I work on a preprocessing tool that does mesh segmentation to convex clusters, uv parametrization, LODs, later maybe low poly for physics, super low poly for occluders, eventually remeshing and material merging.
It really s***s - Simplygon can do all this but i have those special requirements for my GI so i have to care at least for segmentation and UVs myself

[Julio Jerez]

The class looks right, it is working?

adding point to the hull is very easy. I never made into a function because I di not find any application.

the dgConvexHull4d does has that function, because build incremental 4d convex hull show in some algorithm of voronoi convexification. Since them I move to a 3d algorithm.
removing a point is not so simple.

what are you doing that you nee to make incremental hulls.
few things.
- notice that not all points in the point array are pat of the hull. only the point that are addressed by index from triangle list are part of the hull.
you can make a pass over the triangle list marking the point that are visited and those will be the vertices.

all faces are triangles, if you want to make a hull of polygons, there is a post process pass that does that. but that's part of the dgMesh, I use it in the dgConvexHull collision shape to optimize the convex collision shapes

[JoeJ]

what are you doing that you nee to make incremental hulls.

My algorithm works like this: Based on curvature, weight edges if the are probable good borders between convex groups of polygons.
Diffuse those edge weights to polygons until every polygon has a weight.
Find local minima of polys to start clustering convex groups of polygons by region growing.

After some growing the next poly may be added to multiple neighbouring groups, and at this point i'd like to test how adding the polygon to each group would affect the convexity to pick the best.
(E.g. by comparing hull volume vs. group volume.)
After that i end up with too many small clusters, so i use a similar methods to merge clusters.

removing a point is not so simple.

Expected that - would need to copy the state of hull object before adding a test polygon.

A mapping from input vertex to hull vertex if it presists, or the hull polygon otherwise.

I think this makes little sense - if you add a point that is already inside the hull, you simply reject it and have no information available to store.
So it's better i build the mapping just with the resulting hull.
Vertex mapping for those that are on the hull would work, and might help me to create the entire mapping more quickly. For interior vertices i need to find the closest point on the hull, or trace along their normal - not sure yet.

The reason i want this is i need to snap the 3D model vertices (actually the lightmap texel centers) to the convex hull of their convex cluster, and from this i can create the data for my GI algorithm. Similar to a low poly physics model i can trade some surface approximization for speed.

[JoeJ]

Hey Julio, i came across this work http://igl.ethz.ch/projects/instant-meshes/ about remeshing which is very interesting.
The algorithm is lightning fast and if you look here https://www.foundry.com/trends/design-visualisation/mitsuba-renderer-instant-meshes there is a picture and they say it can be used for volumetric meshes too (probably also tetrahedrons instead cubes).

May be interesting for your softbody stuff. There are also other papers about polycubes and similar stuff, but this one seems to stand out. Unfortunately given demo and code is only about remeshing surfaces.