Instancing Objects -- Data structures

#1

Apologies for the vague title, but I can’t summarize my question in a few words.

I’m trying to figure out the best way to instance objects within my homebrew renderer (C++) without incuring too much overhead. I would also like to make the relationship between an object and an instance of an object as transparent as possible to the ray-hit framework.

Question 1) Where’s the best place to store an object’s scaling/translation/rotation matrixes. It seems to me that an object’s coordinates should remain in “object space (OS)”, thus an object’s OS position and orientation should be contained within it’s class.

And if an object isn’t instanced, then it should be ok to keep the matrixes required to move the object into “world space (WS)”.

But, if an object is instanced, then it seems rational to me to keep the matrixes in a seperate object (say InstanceObject) along with a pointer to the object. This way, we only have to load all of the polygons, splines, whatever into the object once, then create an InstanceObject object, passing in the pointer and a string as an identifier, and assign it a bunch of matrixes.

This leads me to question 2…

  1. Will this method bring my CPU to its knees?

If I were to implement such a system, then everytime that a ray/object-boundingvolume is encountered, then I’ll have to calculate all of those matrix translations/etc… on the fly. I really don’t like that idea very much.

Below are some snippets of a few of my class headers. Hopefully they’ll help illustrate the path that I’m taking, and maybe someone will notice any logic errors.

First, the class header to my Abstract Base Class, the “obj” class:


class obj
{
public:
        virtual ~obj() {};

        virtual bool hit( const Imath::V3f & p ) = 0;
        virtual const Imath::V3f & normal() = 0;
        virtual const Imath::Sphere3f & getSphere() const { return _sphere; };

protected:
        Imath::Sphere3f         _sphere;
};

Now the ObjInstance class, used to hold the matrixes and pointer to the object:
A class to hold a group of “obj” pointers:



class ObjGroup
{
public:
        ObjGroup( const char * groupName );

        bool addMember( obj * o );
        unsigned int count() const;

private:
        std::deque< obj * >     _objList;

};



class ObjInstance
{
public:
        ObjInstance( ObjGroup * group, const char * groupName );
        virtual ~ObjInstance();

        const char * getName() const;
        const ObjGroup * getObjGroup() const;

        void setTranslationMatrix( const Imath::M44f & translationMatrix );
        void setRotationMatrix( const Imath::M44f & rotationMatrix );
        void setScaleMatrix( const Imath::M44f & scaleMatrix );

        const Imath::M44f & getTranslationMatrix() const;
        const Imath::M44f & getRotationMatrix() const;
        const Imath::M44f & getScaleMatrix() const;

        typedef std::pair< const char *, ObjGroup * > InstancePair;
private:
        InstancePair    _pair;
        Imath::M44f     _translationMatrix;
        Imath::M44f     _rotationMatrix;
        Imath::M44f     _scaleMatrix;

};

And finally, a typedef to hold all of the instances:


typedef std::map< const char *, ObjGroup * > ObjGroupMap;
ObjGroupMap instanceDB;

It’s late, and I may not have been as clear as I could’ve been during more reasonable hours, but this is driving me crazy. Any help/pointers would be greatly appreciated.

#2

But, if an object is instanced, then it seems rational to me to keep the matrixes in a seperate object (say InstanceObject) along with a pointer to the object. This way, we only have to load all of the polygons, splines, whatever into the object once, then create an InstanceObject object, passing in the pointer and a string as an identifier, and assign it a bunch of matrixes.
Correct. You may also consider storing material assignments in the instance object and have your raytracing acceleration structure be local to the object (so that it does not have to be recreated unless the tesselation of the object is different on each instance). Note, however, that keeping local acceleration structures per object may also give you headaches when multiple objects overlap each other and could end up being counterproductive if you do adaptive tesselations.

No. Your reasoning is correct so far, but you have not thought it through.
You only need to do a single matrix calculation per object and, what’s more, you really can get away without needing to apply the transformation to every single vertex of the object.
Think about it a little bit more (hint: approach the problem in the opposite way). If not clear, do some reviewing on coordinate systems, vectors and matrices.
If still not clear, ask again.

Okay, from quickly glancing at the code, I would recommend you pick up a book on matrix math. You may also consider Matt Pharr’s raytracing book, as he explains this quite nicely.
First, you don’t need to keep 3 different matrices. One of the nice properties of matrices is that they can get concatenated, so you only need a single matrix per object to express its full transformation (translation/rotation/scaling/shears, etc). In raytracers, it is also sometimes useful to keep the inverse matrix of the transform, too.
If you need to get/set rotation/translation/scaling of the matrix, there are well known routines to do so (check out the graphic gems books, but if you are using ILM’s Imath, I’m pretty sure Florian had some methods to extract that information).
Also, for standard rotation/translation/scaling, a 3x3 matrix may also be enough for your needs.

#3

You can transform the ray into object space and do hit-testing there. This way you can use the same vertex data for each instance, just different world->object matrices. Then once you have the hit location, go back to world or eye space for shading.

#4

Gack-- That makes perfect sense. Thanks for knocking some sense into me.

Of course. The supplied header files were only rough-drafts. After thinking a bit on the subject I’d already removed them for a single transformation matrix. And as per noted, there’s an inverse matrix for moving the ray back into world space.

Yes, I’m still tossing some design ideas regarding this around.

Thanks for letting me bounce some ideas off of you guys. I don’t usually ask when the answers are readily available, but this time I wanted to recreate the wheel in order to really learn the material. I find that if I have the answers available (ie source code/book) then I end up glossing over sections. This way I can’t gloss over anything.

Cheers!

#5

This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.