Frozen Sketch and Possible Memory Leak

#1

I’ve been working on a simple gift wrapping algorithm. That Dan Shiffman explored on the coding train live stream a couple of days ago. The gift wrapping works fine however when I tried to modify the input points every time through update I started experiencing bugs. I got a std::bad_alloc exception and an apparent memory leak in the visual studio debugger. This exception only happens in Release mode. See screen shot below. When in debug mode the program freezes immediately (not after 20 seconds) but didn’t crash in the 5 minutes I left it running.

bug

I’ve identified that the problem is either in the generatePoints() or randomizePoints() methods. When I comment out randomizePoints() in update the sketch seems to run smoothly though it doesn’t do much. It seems likely that there’s something wrong with the way I pass things by reference. I’ve tried to keep thinks stack allocated for simplicity but that might be the source of my problem. I’m a little more familiar with c than c++ but overall I’m still quite new to both. Any advice would be greatly appreciated. See the code below.

ofApp.h

#pragma once

#include "ofMain.h"

#define SKETCH_NAME "Gift Wrap"
#define CREATOR "Fi Graham"

class ofApp : public ofBaseApp {
public:

	vector<ofPoint> pointSet;
	vector<int> hull;

	// openFrameworks
	void setup();
	void update();
	void draw();

	// Title
	void setTitle();

	// Points
	void generatePoints(vector<ofPoint> &points, int numberOfPoints, float padding);
	void randomizePoints(vector<ofPoint> &points, float scale, float padding);
	void drawPoints(vector<ofPoint> &points, float radius);
	void drawHull(vector<ofPoint> &points, vector<int> &hull);

	int getLeftMost(vector<ofPoint> &points);
	bool calcNextHullPoint(vector<ofPoint> &points, vector<int> &hull);
	void calcHull(vector<ofPoint> &points, vector<int> &hull);
		
};

ofApp.cpp

#include "ofApp.h"

#define HULL_LAST hull.size() - 1

//--------------------------------------------------------------
// openFrameworks

void ofApp::setup() {
	ofBackground(ofColor::black);
	generatePoints(pointSet, 100, ofGetWidth() / 8);
}

void ofApp::update() {
	setTitle();
	randomizePoints(pointSet, 10, ofGetWidth() / 8);
    calcHull(pointSet, hull);
}

void ofApp::draw() {
	ofSetColor(ofColor::white);
	drawPoints(pointSet, 3);
	ofSetColor(ofColor::purple);
	drawHull(pointSet, hull);
}

//--------------------------------------------------------------
// Title

inline void ofApp::setTitle() {
	stringstream titleStream;
	titleStream << SKETCH_NAME << " - " << CREATOR << " - FPS: " << static_cast<int>(ofGetFrameRate()) << " - Frame: " << ofGetFrameNum();
	ofSetWindowTitle(titleStream.str());
}

//--------------------------------------------------------------
// Points

void ofApp::generatePoints(vector<ofPoint> &points, int numberOfPoints, float padding) {
	points.clear();
	for (int i = 0; i < numberOfPoints; i++) {
		points.push_back(ofPoint(ofRandom(padding, ofGetWidth() - padding), ofRandom(padding, ofGetHeight() - padding)));
	}
}

void ofApp::randomizePoints(vector<ofPoint> &points, float scale, float padding) {
	for (int i = 0; i < points.size(); i++) {
		points[i].x = ofClamp(points[i].x + ofRandom(-scale, scale), padding, ofGetWidth() - padding);
		points[i].y = ofClamp(points[i].y + ofRandom(-scale, scale), padding, ofGetHeight() - padding);
	}
}

void ofApp::drawPoints(vector<ofPoint> &points, float radius) {
	for (int i = 0; i < points.size(); i++) {
		ofDrawCircle(points[i], radius);
	}
}

void ofApp::drawHull(vector<ofPoint> &points, vector<int> &hull) {
	for (int i = 1; i < hull.size(); i++) {
		ofDrawLine(points[hull[i - 1]], points[hull[i]]);
	}
}

int ofApp::getLeftMost(vector<ofPoint> &points) {
	int leftIndex = 0;
	for (int i = 1; i < points.size(); i++) {
		if (points[i].x < points[leftIndex].x) leftIndex = i;
	}
	return leftIndex;
}

bool ofApp::calcNextHullPoint(vector<ofPoint> &points, vector<int> &hull) {
	if (hull.size() > 1 && hull[0] == hull[HULL_LAST]) return true; // returns true hull is complete

	int nextIndex = 0;
	for (int i = 0; i < points.size(); i++) {
		if (i != hull[HULL_LAST] || i != nextIndex) {
			ofVec3f next(points[nextIndex].x, points[nextIndex].y);
			next -= points[hull[HULL_LAST]];
			ofVec3f checking(points[i].x, points[i].y);
			checking -= points[hull[HULL_LAST]];
			ofVec3f cross = next.cross(checking);
			if (cross.z < 0) {
				nextIndex = i;
			}
		}
	}

	hull.push_back(nextIndex);
	return false;
}

void ofApp::calcHull(vector<ofPoint> &points, vector<int> &hull) {
	hull.clear();
	hull.push_back(getLeftMost(pointSet));
	bool done = false;
	while (!done) {
		done = calcNextHullPoint(points, hull);
	}
}

main.cpp

#include "ofMain.h"
#include "ofApp.h"

//========================================================================
int main( ){
	ofSetupOpenGL(540,540,OF_WINDOW);
	ofRunApp(new ofApp());
}

Running Windows 10, Visual Studio Community 2017 v15.9.9, and openFrameworks v0.10.1_vs2017_release

#2

Hi,

randomizePoints is not really complicated, so I made a test removing calcHull : no freeze.

A simple test show that something is wrong:

void ofApp::calcHull( vector< ofPoint > & points, vector< int > & hull )
{
	int cnt = 0 ;
	bool warning = false ;
	hull.clear() ;
	hull.push_back( getLeftMost( pointSet ) ) ;
	bool done = false ;
	while( ! done && ! warning )
	{
		done = calcNextHullPoint( points, hull ) ;
		cnt++ ;
		if( cnt > points.size() * 10 ) warning = true ; // suspicious
	}
	if( warning ) ofLogError() << "Problem with calcHull ?" ;
}

If you watch hull in the debugger, you can see its size become huge when the app freeze.
There’s something wrong in calcNextHullPoint.

I don’t know how to fix it, but here’s an old test app I made once that compute differently the convex hull (draw points with the mouse), you can try to use it in your app. I don’t remember where I have found this code, I can’t credit the author :confused:

src.zip (1,8 Ko)

1 Like
#3

Hi, I´ve never been much of a fan of while loops, and it seems that the problem is inside one. I would try to refactor the calcHull function and put inside of it all that is inside calcNextHullPoint and avoiding the while loops. If the while loop is giving problems then it must be something about how you are checking the loop.

Also, as the points vector is inside your ofApp class there is no need to pass it to the member functions as a reference, which also happens to be named points which could lead into some confusion.

1 Like
#4

@lilive and @roymacdonald Thanks for the advice I’ll look at refactoring my calcHull() function.

The whole passing by reference is something I’ve been learning in my c class recently so I wanted to practice but I think Roy is right that it’s doesn’t make sense for this application. I might try to put everything into a class.

If I get something that works in the next few days I’ll post it for other’s who might find this thread.