A Rare Error

In the course of my research, I encountered the following error and was unable to find any reference to solutions.  However, this error is likely confined to programmers writing their own types using reflection or perhaps a buggy compiler.

PEVerify - "call to .ctor only allowed to initialize this pointer ..."

This error signifies that a constructor (.ctor) should call the constructor for itself or for the type it is extending; however, it is directly calling a different routine.  The following code is a rough sketch of the error condition.

class baseT  // implicitly derives from Object

{

    baseT() { }

}

class derT : baseT

{

    derT()

    {

        Object();  // calling a different constructor than base class

    }

}

For my work, changing the call from Object() to baseT() fixed the error.

Ray Tracing Performance and Practice Part 3

When last we left the ray tracer, it could read in PLY files and then render a scene.  But while it rendered, you'd probably want to get dinner, read some blogs, and write some code.  Very slow.  Improving performance is very straight forward: either reduce the work done or find a way to do the same work faster.

At the time of original development, I knew that there existed further performance opportunities via Oct Trees.  The idea behind these and other similar structures is to partition the scene into sub-scenes that can be treated in the aggregate.  Let's work through a simple example.

While the actual ray tracer is in 3D, we'll reason through a 2D tracer.  We'll have lots of circles and triangles in standard XY coordinates.  We can start partitioning the scene into quadrants: +X +Y, +X -Y, etc.  Now, when we draw a line (i.e., the ray) through the scene, rather than checking whether the ray is intersecting every circle and triangle, we can first check whether it is passing through any quadrant.  If the ray doesn't pass through the quadrant, then the ray will also not pass through any object in the quadrant.  The Oct Trees work very similarly, except besides X and Y, the scene is also split by +/- Z.

If the scene is split just once, this can likely provide some benefit, but for real practicality each octant of the tree must also be split repeatedly until only a few scene objects (i.e., spheres and triangles) remain in each octant.  This is all well and good; however, four particular problems arise: first, where should each octant be split.  Second, how many scene objects should be in each octant.  Third, how should objects that straddle octant boundaries be handled?  Finally, how does one practically render with an Oct Tree?

Where?  Two possibilities were tried: splitting in the "center" of the objects and splitting in the center of the octant.  If the split point is based on the objects, then each octant should have a similar number of objects.  This bounds the depth of the Oct Tree by making each octant have a subset of the parent octant.  However, this also forces every ray to traverse several levels of the Oct Tree, as every octant should contain scene objects.  Instead, if each octant is split at its center, then many octants may be empty, but the ones with scene objects may have significant number of levels in the tree before reaching individual objects.

How many?  Ideally, this number would be reached based on considerable experimentation and analysis.  At present, the code just splits an octant when it contains more than 16 scene objects.  Given the 50k triangle scene from the previous post, this would create roughly 3000 final octants, 375 parent octants, 47 grandparents, 6 great grandparents, and 1 root.  Ideally.

Yet, the split points are never ideal and so the octants are imbalanced.  Especially as some scene objects will cross the octant boundaries.  For example, a sphere placed at the origin is present in all 8 octants.  So the Oct Tree places the scene object into every octant that it is present within.  Rather than computing whether the object is precisely within the octant, the Oct Tree creates a bounding cube around the object.  Back to the 2D space, draw a triangle from (1,1), (-1, 1), and (-1, -1).  A square around this triangle would also include (1, -1), and therefore the triangle would also be "part" of the +X -Y quadrant.  I would be happy to switch to computing whether the object intersects the octant boundary planes; however, that would be when I understand the math involved.

The final issue is how to put the Oct Tree into practice.  In the immediate, the intersect code follows:

    if (No Octants) 

        foreach SceneObject in OctTree

        {

            Compute Distance for Ray to Intersect Object

        }

        Return closest object or none

    foreach Octant in OctTree {

        Compute Distance for Ray to intersect Octant

    }

    Sort Distances

    Select closest octant

    do {

        Recurse on octant

        if (Object returned) return object

        Select next closest octant

    } while (Octants remain)

    return none

A potential optimization is to handle shadows, reflected rays, etc from the lowest octant rather than starting at the root.  However, implementing such an optimization requires significant state tracking, which also impedes making the ray tracer multi-threaded.

In a future part 4, I'll explore the hurdles of making the tracer multi-threaded rather than its current implementation of one thread.

Accessing Structs with Side Effects

In my recent research, I've needed to take certain additional actions when the fields in a data structure are changed.  Since all code involved is my own, my initial approach was to annotate any access with explicit calls.  Obviously, this isn't sustainable in larger projects, but for quick prototyping, it is sufficient.  Let's see a simple example (with pseudo-C as usual):

typedef struct _tree {

    pTree left, right;

    int data;

} Tree, *pTree;

Tree t;

t.left = t.right = NULL;

// Now take action

Since we want to ensure that we take action after every update, get / set routines could be introduced for each field.  Yet, now I have the overhead of calling these routines on every access.  And I still have to trust that all accesses will use the routines (though using another language like C++, I could make the fields private and force access to the routines).

My research is currently using C#, so I have further tools available to me, specifically accessors.  Initially, they seemed to be yet another silly hoop to jump through while writing code.  However, they provide a great tool for my present problem, where modifications to fields need to incur side effects.  Now for a C# snippet:

private Node pLeft;  // Internal storage

public Node left     // Public accessor
{
    get { return pLeft;}
    set
    {
        if (pLeft == value) return;  // discard redundant stores
        pLeft = value;
        pStack.Push(this); // side effect on update

    }

}

So my data structure now has implicit side effects from updates (good for the research).  And so any future development doesn't need explicit annotations.  All in all, I was quite pleased with this change (except for spending the time debugging the differences between implicit and explicit detection).

Stack Overflow: String Replace

I've recently begun exploring Stack Overflow.  Helping to answer people's questions has a considerable appeal to one, such as I, who enjoys teaching.  Sometimes you can find a question that no one has answered, as few know the answer.  Other times, almost any professional programmer can answer the question, and often these are from CS students trying to solve their homework.  On occasion, I may repost interesting questions here.

For my first repost, we have a StringReplace function that needs optimizing.  Independent of the questioner's implementation, let's consider the core algorithm.

StringReplace(OldText, NewText, BaseString)

    for SubString of length OldText in BaseString

        if (OldText == SubString) {Replace text}

This is how we want to replace.  Find each instance of OldText in BaseString and replace.  Given the nature of the question, our implementation will be written in C and not use any libraries (like regex, CRT, etc).

Working backwards, we'll need to return a final string of some indeterminate size.  Then the BaseString, as it is modified, is stored in this final string, in the following form, where each base is a subset of the string:

When the problem is viewed this way, an implementation is suggested, recursive.  The following code expands upon this approach (though avoiding some casting requirements, necessities of sizeof(char), and possibility of unicode support).

#define StringReplace(x, y, z) StringReplaceHelper(x, y, z, 0)

char* StringReplaceHelper(char* OldText, 

                          char* NewText, 

                          char* BaseString,

                          unsigned long space)

{

    char* start = BaseString, ret = NULL;

    unsigned long offset = 0;

    while (*BaseString != '\0')

    {

        if (Match(OldText, BaseString))

        {

             offset = (BaseString - start);

             // The next search will begin after 

             // the replacement text

             ret = StringReplaceHelper(OldText, NewText,

                                 BaseString + strlen(OldText), 

                                 space + offset + strlen(NewText));

             break;

        }

        BaseString++;

    }

    // If the end of string, then this is the last piece

    // Else copy in subset and replacement piece

    if (*BaseString == '\0')

    {

        offset = (BaseString - start);

        ret = (char*) malloc((space + offset));

        memcpy(ret + space, start, offset));

    }

    else

    {

        memcpy(ret + space, start, offset);

        // Don't actually do the following, the processor

        // will have to walk NewText twice

        memcpy(ret + offset, NewText, strlen(NewText));

    }

    return ret;

}

First, the routine Match() is basically a string compare, which can have its own interesting optimizations including partial skip-ahead.  Second, a final version wouldn't use strlen, except perhaps at the start.  The lengths can be passed between iterations.  Finally, using memcpy and malloc aren't cheating as I've written my own implementations in the past, and therefore their omission in the present is just for the sake of brevity.

But this is just what I'd currently write for a string replace.  You can follow the link to Stack Overflow and see the original request (and my suggestion for improvement).  Or perhaps consider your own.

Object-Oriented C (part 2)

In part 1, I outlined the problem with writing a ray tracer in C, particularly how to opaque the presence of different objects.  Since my roommate was a TA, he and I discussed some of the crude ways he feared that he would have to grade.  For example, the intersect calls might be based on switch ... case or an if ... else chain, as follows:

switch (object->type)

{

    case TRIANGLE: ...

    case SPHERE: ...

...

}

While it clearly handles the different object types, it sets up regular patterns of duplicated code.  Once for intersection, then for finding a color, etc.  Each pattern also has to be modified if a new scene object is introduced.  But I wanted something better, particularly I wanted to show that carrying a type field is unnecessary for my design.  I concluded that I could have my scene objects carry their function pointers.  (Note, the following code is still pseudo in nature and is provided for illustration and not compilation purposes).

typedef struct _SCENE_OBJECT {

    float (*Intersect) (pSCENE_OBJECT, Vec3);

    void (*Color) (pSCENE_OBJECT, Vec3 ...);

    pSCENE_OBJECT next;

} SCENE_OBJECT, *pSCENE_OBJECT;

Then I declare my sphere scene object (and similarly for other scene objects), as follows:

typedef struct _SCENE_OBJECT_SPHERE {

    SCENE_OBJECT generic;

    ....

} SCENE_OBJECT_SPHERE, *pSCENE_OBJECT_SPHERE;

Now, my scene object types have inherited from the base object.  Therefore, the intersection loop from part one now has a single line intersection call:

dist = object->Intersect(object, ray);

This approach still has drawbacks, but it achieves a simple inheritance between structs in C, thereby providing a rudimentary OO capability to a language known for not having one.  In part 3, I look forward to exploring some of the drawbacks, as well as the elusive discussion of how OO intrinsically works in C++ or other languages.

Object-Oriented C (part 1)

For most programmers, the very idea of writing object-oriented (OO) C code seems wrong on several levels.  First, there are several, quite usable, programming languages that already support OO designs, so why mess with adding something to C that is as core to a language as OO?  Second, how would someone do this anyway?

Disclaimer: I am not recommending that OO programming be generally accomplished in C, but rather am writing to argue how some OO constructs can be integrated into a program to improve its design / readability (i.e., elegance).

Many years ago when I was an undergraduate in Computer Science, one assigned project was to write a ray tracer.  The provided framework was in C++, but having not studied the details of inheritance, overloading, etc, I elected to rewrite the framework in C.  Since the framework was very simple, the few classes were merely renamed to struct and member functions provided a prefix.  Yet, this is not the interesting part, merely the starting point.

In brief, ray tracers cast (i.e., test for intersection) a ray (i.e., vector) against the scene (i.e., a list of objects).  The object that is first intersected provides the color for that part of the image.  Different objects will have different intersection tests / other properties.  In pseudo-C, the code for intersection might read:

object = objectList->head;

minDist = INF;  minObject = NULL;

while (object != NULL) {

    dist = Intersect(object, ray);

    if (dist < minDist) {... }

    object = object->next;

}

The fundamental design problem is therefore how to properly set up the objects so that the ray tracer's operations upon its scene objects are still elegant.  How to accomplish this will be discussed in part 2, along with how OO intrinsically works.